Kiến kiếm ăn sang phải

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; giá trị âm nghĩa là ô đó có bẫy làm kiến mất thức ăn.

Kiến chọn một ô bất kỳ ở cột \(1\) để xuất phát. Từ ô \((i, j)\), mỗi bước kiến chỉ sang một trong ba ô ở cột ngay bên phải: \((i-1, j+1)\), \((i, j+1)\) hoặc \((i+1, j+1)\) (không được ra ngoài sân). Kiến kết thúc khi đến cột \(N\). Tổng thức ăn thu được là tổng các giá trị trên các ô đi qua, kể cả ô xuất phát.

Hãy tìm tổng lớn nhất có thể đạt đượ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: tổng lớn nhất.

Constraints

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

Sample Input

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

Sample Output

26

Explanation

Đường đi tốt nhất là \((2,1) \to (3,2) \to (2,3) \to (3,4) \to (2,5)\) với tổng \(8 + 7 + 4 + 5 + 2 = 26\).