#include <cstdio>
#include <cassert>
#define Nmax 1005
#define InFile "ferma2.in"
#define OutFile "ferma2.out"

using namespace std;

int n, K;
int N[Nmax][Nmax], lin[Nmax][Nmax], col[Nmax][Nmax], diag[Nmax][Nmax];
int M[2][Nmax][Nmax];

void read();
void sume();
void solve();

int main()
{
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  read();
  sume();
  solve();
  return 0;
}

void read()
{
  int i, j;
  scanf ("%d %d\n", &n, &K);
  for (i=1; i<=n; i++)
    for (j=1; j<=i; j++)
      scanf ("%d\n", &N[i][j]);
}

void sume()
{
  int i, j, k;
  //linii
  for (i=1; i<=n; i++)
    for (j=1; j<=i; j++)
      lin[i][j]=lin[i][j-1]+N[i][j];

  //coloane
  for (j=1; j<=n; j++)
    for (i=j; i<=n; i++)
      col[i][j]=col[i-1][j]+N[i][j];
    
  //diagonale
  for (i=1; i<=n; i++)
    for (j=i, k=1; j<=n; j++, k++)
      diag[j][k]=diag[j-1][k-1]+N[j][k];
}

void solve()
{
  int z, i, j, cr=1, ant=0, k=n-K+1, Max, nr;
  for (z=1; z<=K; z++)
  {
    for (i=k; i<=n; i++)
      for (j=1; j<=i-k+1; j++)
      {
        Max=M[ant][i-1][j]+(lin[i][j+k]-lin[i][j]);
        
        nr=M[ant][i][j+1]+(col[i][j]-col[i-k][j]);
        if (nr>Max) Max=nr;
          
        nr=M[ant][i][j]+(diag[i][j+k-1]-diag[i-k][j-1]);
        if (nr>Max) Max=nr;
        M[cr][i][j]=Max;
      }
    k++; ant^=1; cr^=1;
  }
  printf ("%d\n", M[ant][n][1]);
}