Đường đi trên lưới

Một trò chơi diễn ra trên bảng hình chữ nhật \(M\) dòng, \(N\) cột; ô \((i, j)\) chứa số nguyên \(a_{i,j}\) (có thể âm). Người chơi chọn một ô bất kỳ ở cột \(1\) làm điểm xuất phát, sau đó mỗi bước sang cột kế tiếp bằng cách đi vào một trong ba ô: chéo lên \((i-1, j+1)\), ngang \((i, j+1)\) hoặc chéo xuống \((i+1, j+1)\) (không được ra ngoài bảng), cho đến khi tới cột \(N\).

Điểm của một cách chơi là tổng các số ghi trong tất cả các ô đã đi qua (kể cả ô xuất phát; ô mang số âm làm giảm điểm). Hãy tìm điểm lớn nhất.

Input

• Dòng đầu: hai số nguyên \(M, N\).
• \(M\) dòng tiếp theo, mỗi dòng \(N\) số nguyên \(a_{i,j}\).

Output

Một số nguyên: điểm lớn nhất có thể đạt được.

Constraints

• \(1 \le M, N \le 300\)
• \(-10^5 \le a_{i,j} \le 10^5\)
• \(50\%\) số test có \(M, N \le 100\).

Sample Input

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

Sample Output

23

Explanation

Đi theo các hàng \(3, 2, 1, 1, 2\) (từ cột \(1\) đến cột \(5\)): \(7 + 5 + 1 + 6 + 4 = 23\), và đây là giá trị lớn nhất.