#include <iostream>
#include <fstream>
#define DEBUG 0
#define MAXN 1000

using namespace std;

int m[MAXN][MAXN], sumc[MAXN][MAXN], suml[MAXN][MAXN], sumd[MAXN][MAXN], d[MAXN][MAXN];

int main(){
  int n, k, l, sumt = 0;

  ifstream fin ("ferma2.in");
  fin >> n >> k;
  l = n - k;

  for(int i = 0; i < n; i ++){
    for(int j = 0; j <= i; j ++){
      fin >> m[i][j];
      sumt += m[i][j];
    }
  }
  fin.close();

  // Precalculare sume pe linii
  for(int i = l - 1; i < n; i ++){
    int j = 0, sum = 0;
    while(j < l){
      sum += m[i][j];
      j ++;
    }
    suml[i][j - l] = sum;

    while(j <= i){
      sum = sum + m[i][j] - m[i][j - l];
      j ++;
      suml[i][j - l] = sum;
    }
  }

  // Precalculare sume pe coloane
  for(int j = 0; j <= n - l; j ++){
    int i = j, sum = 0;
    while(i < j + l){
      sum += m[i][j];
      i ++;
    }
    sumc[i - l][j] = sum;

    while(i < n){
      sum = sum + m[i][j] - m[i - l][j];
      i ++;
      sumc[i - l][j] = sum;
    }
  }

  // Precalculare sume pe diagonale
  for(int i = 0; i <= n - l; i ++){
    int j = 0, sum = 0;
    while(j < l){
      sum += m[i + j][j];
      j ++;
    }
    sumd[i + j - l][j - l] = sum;

    while(i + j < n){
      sum = sum - m[i + j - l][j - l] + m[i + j][j];
      j ++;
      sumd[i + j - l][j - l] = sum;
    }
  }

  if(DEBUG){
    for(int i = 0; i < n; i ++){
      for(int j = 0; j <= i; j ++){
        printf("%d ", m[i][j]);
      }
      printf("\n");
    }
    printf("\nsuml:\n");
    for(int i = 0; i < n; i ++){
      for(int j = 0; j <= i; j ++){
        printf("%d ", suml[i][j]);
      }
      printf("\n");
    }
    printf("\nsumc:\n");
    for(int i = 0; i < n; i ++){
      for(int j = 0; j <= i; j ++){
        printf("%d ", sumc[i][j]);
      }
      printf("\n");
    }
    printf("\nsumd:\n");
    for(int i = 0; i < n; i ++){
      for(int j = 0; j <= i; j ++){
        printf("%d ", sumd[i][j]);
      }
      printf("\n");
    }
    printf("\n");
  }

  int sum = 0;
  for(int i = 0; i < l; i ++){
    for(int j = 0; j <= i; j ++)
      sum += m[i][j];
  }
  d[0][0] = sum;

  for(int i = 1; i <= n - l; i ++){
    d[i][0] = d[i - 1][0] + suml[i + l - 1][0] - sumd[i - 1][0];
    for(int j = 1; j <= i; j ++){
      d[i][j] = d[i][j - 1] - sumc[i][j - 1] + sumd[i][j];
    }
  }

  int min = d[0][0];
  for(int i = 1; i <= n - l; i ++)
    for(int j = 0; j <= i; j ++)
      if(d[i][j] < min)
        min = d[i][j];
        

  if(DEBUG){
    for(int i = 0; i < n; i ++){
      for(int j = 0; j <= i; j ++){
        printf("%d ", d[i][j]);
      }
      printf("\n");
    }
    printf("\n");
  }

  ofstream fout ("ferma2.out");
  fout << sumt - min << endl;
  fout.close();

  return 0;
}