(*

Il triangolo (IOI 1994)
Copyright (C) 2000 Paolo Boldi

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*)

program Ioi9411;
(* Il triangolo viene memorizzato in un array.
   Notate che la riga r ha r elementi: il suo primo elemento e' preceduto
   da 1+2+...+(r-1) elementi e ha quindi indice r(r-1)/2+1=(r^2-r+2)/2.
   Il suo ultimo elemento ha indice (r^2+r)/2. *)


const
     maxr=100;
     maxel=5050; (* Massimo valore di r^2+r *)
     nomefin='input-6.txt';
     nomefout='myout-6.txt';
var
   nr: byte; (* Numero di righe *)
   t: array [1..maxel] of word; (* Triangolo *)

function max(a,b: word): word;
begin
     if (a>b) then max:=a else max:=b
end;

procedure maxsomma;
(* Calcola le massime somme "sul posto" *)
var r,i: byte;
    index: word;
begin
     index:=trunc((sqr(nr-1)+nr-1)/2); (* Indice ult. elemento penultima riga *)
     for r:=nr-1 downto 1 do
         for i:=r downto 1 do
             begin
                  (* Calcolo il valore max relativo all'i-esimo elem. della riga r,
                     il cui indice e' index *)
                  t[index]:=t[index]+max(t[index+r],t[index+r+1]);
                  dec(index)
             end
end;

procedure inp;
(* Legge l'input nell'array t *)
var f: text;
    i,j: byte;
    u: word;
begin
     assign(f,nomefin);
     reset(f);
     read(f,nr);
     u:=0;
     for i:=1 to nr do
         for j:=1 to i do
             begin
                  inc(u);
                  read(f,t[u])
             end;
     close(f)
end;

(* MAIN *)
var f: text;
begin
     inp;
     maxsomma;
     assign(f,nomefout);
     rewrite(f);
     writeln(f,t[1]);
     close(f)
end.