var  n,m,i,j,x,k,y:longint;
     a:array[1..2500]of longint;
     g:array[0..500,1..2500]of boolean;
     f:array[0..500]of longint;
begin
assign(input,'skill.in');reset(input);
assign(output,'skill.out');rewrite(output);
readln(n,m);
fillchar(a,sizeof(a),0);
for i:=1 to n do
   for j:=1 to n+1-i do
     begin
     read(x);
     a[(i-1)*n+j]:=x;
     end;
fillchar(g,sizeof(g),false);
x:=((1+n)*n) div 2;
y:=0;
if m=1 then
 begin
 for i:=1 to n do   if a[i]>y then y:=a[i];
 writeln(y);
 end
else begin
 for i:=1 to x do
     for j:=m-1 downto 0 do
       if f[j]+a[i]>f[j+1] then

         f[j+1]:=f[j]+a[i];


 writeln(f[m]);
 end;
close(input);close(output)
end.