program ioi94day1prb1ver2(input, output, inp, out) ;
{ Tom Verhoeff, Eindhoven University of Technology }
{ Efficient recursive solution with memorization }


{ General Section }

const
  Test = true ;

var
  inp, out: text ;

procedure Init ;
  begin
  if Test then
    writeln('IOI''94 - Day 1 - Problem 1: The Triangle') ;
  assign(inp, 'input.txt') ;
  reset(inp) ;
  assign(out, 'output.txt') ;
  rewrite(out) ;
  if Test then writeln('Initialized')
  end { Init } ;

procedure Fini ;
  begin
  close(inp) ;
  close(out)
  end { Fini } ;


{ Problem Specific Section }

const
  MaxN = 100 ;

type
  index = 1..MaxN ;
  number = 0..99 ;

var
  N: index ; { number of rows }
  T: array [index, index] of number ;
    { T[r, p] is the number in row r at position p }
  MRS: array [index, index] of integer ;
    { MRS[r, p] is the maximum sum for routes from T[r, p], or -1 if unknown }
  m: integer ; { maximum route sum }

procedure ReadInput ;
  { read N and T[r, p] with  1 <= r <= N  and  1 <= p <= r }
  { initialize all relevant MRS[r, p] at -1 }
  var r, p: index ;
  begin
  readln(inp, N) ;
  if Test then writeln('Number of rows is ', N:1) ;
  for r := 1 to N do begin
    for p := 1 to r do begin
      read(inp, T[r, p]) ;
      MRS[r, p] := -1
      end { for p } ;
    readln(inp)
    end { for r } ;
  if Test then writeln('All input read')
  end { ReadInput } ;

procedure ComputeAnswer ;
  { m := the maximum route sum }

  function Max(x, y: integer): integer ;
    begin if x > y then Max := x else Max := y end { Max } ;

  function MaxRS(r, p: index): integer ;
    { return maximum sum over all down routes starting in T[r, p] }
    begin
    if MRS[r, p] = -1 then
      if r = N then MRS[r, p] := T[r, p]
      else MRS[r, p] := T[r, p] + Max(MaxRS(r+1, p), MaxRS(r+1, p+1)) ;
    MaxRS := MRS[r, p]
    end { MaxRS } ;

  begin
  m := MaxRS(1, 1)
  end { ComputeAnswer } ;

procedure WriteOutput ;
  begin
  writeln(out, m:1) ;
  if Test then writeln('The maximum route sum is ', m:1)
  end { WriteOutput } ;

begin
Init ;
ReadInput ;
ComputeAnswer ;
WriteOutput ;
Fini
end.
