program cc;
var
i,j,k,n,max,maxf:longint;
a:array[0..80,0..80] of longint;
f:array[0..80,0..80] of longint;
step:array[1..80,1..80] of longint;
 f1,f2:text;
begin
assign(f1,'shuta.in');reset(f1);
assign(f2,'shuta.out');rewrite(f2);
readln(f1,n);

for i:=1 to n do
begin
inc(k);
for j:=1 to k do
begin
read(f1,a[i,j]);
f[i,j]:=a[i,j];
end;
end;


for i:=n-1 downto 1 do
 for j:=1 to n do
   for k:=j to j+1 do
     if f[i,j]<f[i+1,k]+a[i,j] then
     f[i,j]:=f[i+1,k]+a[i,j];


writeln(f2,f[1,1]);

for i:=1 to n do
begin
 for j:=1 to i do
 if f[i,j]>maxf then begin maxf:=f[i,j];max:=a[i,j];end;
 maxf:=0;
 if i<n then write(f2,max,' ') else write(f2,max);
end;

close(f1);
close(f2);
end.