Cho một bảng \(A\) kích thước \(m \times n\) \((1 \le m,n \le 100)\), trên đó ghi các số nguyên \(a_{i,j}\) \((|a_{i,j}|\le 100)\). Một người xuất phát tại ô nào đó của cột \(1\), cần sang cột \(n\) (tại ô nào cũng được).

Quy tắc đi: Từ ô \((i,j)\) chỉ được quyền đi sang một trong ba ô \((i,j+1)\); \((i-1,j+1)\); \((i+1,j+1)\)

Dữ liệu vào

• Dòng 1: Ghi hai số \(m,n\) là số hàng và số cột của bảng. \(M\) dòng tiếp theo, dòng thứ \(i\) ghi đủ \(n\) số trên hàng \(i\) của bảng theo đúng thứ tự từ trái qua phải

Dữ liệu ra

• Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được

Input 1

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

Output 1

41