记录编号	8182	评测结果	AAAAAAAAAA
题目名称	[BYVoid S3] 艾萨拉的激流	最终得分	100
用户昵称	zpl123	是否通过	通过
代码语言	Pascal	运行时间	4.558 s
提交时间	2008-11-13 11:47:45	内存使用	76.48 MiB

program azshara;
var
f,x:array[1..10000,0..1000] of longint;
w,l:longint;


procedure init;
var
i,j:longint;
begin
assign(input,'azshara.in');
reset(input);
assign(output,'azshara.out');
rewrite(output);
readln(w,l);
for i:=1 to l do
 begin
 for j:=1 to w do read(x[i,j]);
 readln;
 end;
close(input);
end;

procedure main;
var
i,j,t:longint;
begin
for i:=1 to w do if x[l,i]=-1 then f[l,i]:=-1 else f[l,i]:=x[l,i];
for i:=l-1 downto 1 do
 for j:=1 to w do
 begin
 if x[i,j]=-1 then f[i,j]:=-1
  else
  begin
  t:=x[i,j]+f[i+1,j];
  if t<x[i,j]+f[i+1,j+1] then t:=x[i,j]+f[i+1,j+1];
  if t<x[i,j]+f[i+1,j-1] then t:=x[i,j]+f[i+1,j-1];
  f[i,j]:=t;
  t:=0;
  end;
 end;
end;

procedure print;
var
i,ans:longint;
begin
for i:=1 to w do if ans<f[1,i] then ans:=f[1,i];
writeln(ans);
close(output);
end;

begin
init;
main;
print;
end.