#include <stdio.h>
#include <vector>
using namespace std;
#define maxn 1005
vector <int> tri[maxn];//tine triunghiul initial
int dp[maxn][maxn];
int n,k;

int diagonala(int linia, int coloana, int lungimea){
    int suma=0;
    int i;
    for(i=0;i<lungimea;i++)
      suma+=tri[linia+i][i+coloana];
    return suma;
}

int oriz(int linia, int coloana, int lungimea){
   int suma=0;
   int i;
   lungimea+=coloana;
   for(i=coloana;i<lungimea;i++)
       suma+=tri[linia][i];
   return suma;
}

int verticala(int linia, int coloana, int lungimea){
   int suma=0;
   int i;
   for(i=0;i<lungimea;i++)
       suma+=tri[i+linia][coloana];
return suma;
}

int main(){
  FILE *fin=fopen("ferma2.in","r");
  FILE *fout=fopen("ferma2.out","w");
  fscanf(fin,"%d%d",&n,&k);
  int a;
  int i,j;
  int suma=0,suma_totala=0;
  for(i=0;i<n;i++){
    for(j=0;j<=i;j++){
      fscanf(fin,"%d",&a);
      suma_totala+=a;
      tri[i].push_back(a);
    }
  }
  //dp[i][j]=castigul maxim, daca triunghiul care ramane are varful de sus in  [i][j]
     //initializez
     int minim=suma_totala;
     int l=n-k;

     for(i=0;i<l;i++) 
       for(j=0;j<=i;j++)
          suma+=tri[i][j];

     dp[0][0]=suma;
     if(suma<minim)minim=suma;
     for(i=1;i<=k;i++){
       //initializez coloana 0
       dp[i][0]=dp[i-1][0]-diagonala(i-1,0,l)+oriz(i+l-1,0,l);
       if(dp[i][0]<minim)minim=dp[i][0];
       //pt coloanele de la 1 incolo
       for(j=1;j<=i;j++){
           dp[i][j]=dp[i][j-1]+diagonala(i,j,l)-verticala(i,j-1,l);
           if(dp[i][j]<minim)minim=dp[i][j];
       }
     }           

  fprintf(fout,"%d\n",suma_totala-minim);
  return 0;
}