Kiến kiếm ăn đi xuống

Một chú kiến kiếm ăn trên sân trường hình chữ nhật gồm \(M\) hàng và \(N\) cột (hàng đánh số từ \(1\) đến \(M\) từ trên xuống, cột đánh số từ \(1\) đến \(N\) từ trái sang). Ô \((i, j)\) chứa \(a_{i,j}\) đơn vị thức ăn.

Kiến có thể xuất phát tại một ô bất kỳ của hàng \(1\). Từ ô \((i, j)\), mỗi bước kiến chỉ được sang một trong ba ô ở hàng ngay dưới: \((i+1, j-1)\), \((i+1, j)\) hoặc \((i+1, j+1)\) (không được ra ngoài sân). Kiến dừng khi đã đến hàng \(M\) và thu nhặt toàn bộ thức ăn ở các ô đi qua (kể cả ô xuất phát).

Hãy tính lượng thức ăn lớn nhất mà kiến có thể thu được.

Input

• Dòng đầu chứa hai số nguyên \(M\) và \(N\).
• \(M\) dòng tiếp theo, mỗi dòng gồm \(N\) số nguyên \(a_{i,1}, \dots, a_{i,N}\).

Output

• In ra một số nguyên: lượng thức ăn lớn nhất.

Constraints

• \(1 \le M, N \le 1000\)
• \(0 \le a_{i,j} \le 10^9\)

Sample Input

4 3
5 0 7
3 8 2
1 4 6
9 2 2

Sample Output

28

Explanation

Đường đi tối ưu là \((1,3) \to (2,2) \to (3,2) \to (4,1)\) với lượng thức ăn \(7 + 8 + 4 + 9 = 28\).