Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên a_ij (|a_ij| <= 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 sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i + 1, j + 1)

Dữ liệu

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

Kết quả

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