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 aij (|aij| <= 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).

Input

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

Output

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

Example

Input:

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:

41

Em có làm bài đó như sau mà nó ra có 39 à! Mong mọi người giúp đỡ e ạ

Mã:

uses crt;

var m,n,i,j:integer;

a,f:array[0..100,0..100] of integer;

procedure input;

var f:text;

begin

assign(f,'d:\pascal\dgdidai1\input.txt');

reset(f);

readln(f,n,m);

for i:=1 to n do

begin

for j:=1 to m do

read(f,a[i,j]);

readln(f);

end;

end;

function max(a,b:integer):integer;

begin

if a>b then exit(a) else exit(b);

end;

procedure qhd;

begin

fillchar(f,sizeof(f),0);

for i:=1 to n do

for j:=1 to m do

f[i,j]:= max(f[i-1,j-1],max(f[i,j-1],f[i+1,j-1]))+a[i,j];

end;

procedure rslt;

var kq:integer;

begin kq:=-maxint;

for i:=1 to n do

if f[i,m]>kq then kq:=f[i,m];

write(kq);

end;

begin

clrscr;

input;

qhd;

rslt;

readln;

end.