Vợ chồng nhà Thạch Sùng tổ chức một cuộc đi săn muỗi trên một bức tường kích thước \(m \times n\) được chia thành lưới ô vuông đơn vị. Các hàng của lưới được đánh số từ \(1\) đến \(m\) theo thứ tự từ trên xuống dưới, và các cột được đánh số từ \(1\) đến \(n\) theo thứ tự từ trái qua phải. Trên mỗi ô \((i, j)\) của bức tường có \(a[i][j]\) con muỗi.

Vợ chồng Thạch Sùng đang đứng ở mép trên của bức tường. Họ có thể tùy chọn vị trí xuất phát để có thể bò xuống các ô bên dưới để ăn muỗi. Khi Thạch Sùng đi qua một ô nào thì muỗi ở ô đó bị ăn hết. Do tường khá trơn nên từ \(1\) ô trên \(1\) hàng, Thạch Sùng chỉ có thể bò xuống ô ở hàng dưới có chung cạnh hoặc chung đỉnh với ô đang đứng. Khi Thạch Sùng di chuyển xuống đến ô dưới cùng của mép tường, cuộc săn kết thúc.

Vợ chồng Thạch Sùng đang tranh luận xem nên chia nhau ra săn muỗi như thế nào để tổng số muỗi ăn được là lớn nhất. Bạn hãy dự tính tổng số muỗi lớn nhất mà họ có thể ăn được. Tại một thời điểm, hai con Thạch Sùng có thể ở cùng một ô. Số muỗi ăn được là tổng số muỗi trên các ô được đi qua.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương \(m\) và \(n\) (lần lượt là số hàng và số cột của bức tường).
• \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên, số thứ \(j\) trong dòng thứ \(i\) là \(a[i][j]\), biểu thị số muỗi tại ô \((i, j)\).

Dữ liệu ra

• Ghi ra tổng số muỗi mà vợ chồng Thạch Sùng ăn được.

Ràng buộc

• \(1 \le m,n \le 100\)
• \(1 \le a[i][j] \le 10^5\)

Input 1

4 4
0 2 0 1
4 0 5 2
0 4 0 3
0 2 0 2

Output 1

23