#include <stdio.h>
#define MAXN 1000
#define INF 2000000000
int vert[MAXN + 1][MAXN + 1], diag[MAXN + 1][MAXN + 1];

inline int caut(int sum, int k, int i, int j){
  int min = sum;
  while(j <= i){
    sum += diag[i][j] - diag[i - k][j - k];
    sum -= vert[i][j - k] - vert[i - k][j - k];
    if(min > sum)
      min = sum;
    j++;
  }
  return min;
}

int main(){
  FILE *in = fopen("ferma2.in", "r");
  int n, k, i, j, x, sumt = 0;
  fscanf(in, "%d%d", &n, &k);
  k = n - k;
  for(i = 1; i <= n; i++){
    for(j = 1; j <= i; j++){
      fscanf(in, "%d", &x);
      sumt += x;
      vert[i][j] = x + vert[i - 1][j];
      diag[i][j] = x + diag[i - 1][j - 1];
    }
  }
  fclose(in);
  int sum = 0, min = INF;
  for(i = 1; i <= k; i++){
    for(j = 1; j <= i; j++){
      sum += vert[i][j] - vert[i - 1][j];
    }
  }
  if(sum < min)
    min = sum;
  for(i = k + 1; i <= n; i++){
    sum -= diag[i][k + 1];
    for(j = 1; j <= k + 1; j++)
      sum += vert[i][j] - vert[i - 1][j];
    if(min > sum)
      min = sum;
    x = caut(sum, k, i, k + 1);
    if(x < min)
      min = x;
  }
  FILE *out = fopen("ferma2.out", "w");
  fprintf(out, "%d", sumt - min);
  fclose(out);
  return 0;
}