#include <fstream>

using namespace std;

ifstream fin ("ferma2.in");
ofstream fout ("ferma2.out");

int a[1005][1005], col[1005][1005], lin[1005][1005], ipo[1005][1005];
int d, Max, n, k, x;

int main()  {
  fin >> n >> k;
  for (int i = 1; i <= n; ++i)  {
    for (int j = 1; j <= i; ++j)
      fin >> a[i][j];
  }
  for (int j = 1; j <= n; ++j)  {
    int coloana = 0;
    for (int i = 1; i <= n; ++i)  {
      coloana += a[i][j];
      col[i][j] = col[i][j - 1] + coloana;
    }
  }
  for (int i = n; i; --i)  {
    int linie = 0;
    for (int j = 1; j <= i; ++j)  {
      linie += a[i][j];
      lin[i][j] = lin[i + 1][j + 1] + linie;
    }
  }
  for (int q = 0; q < n; ++q)  {
    int diag = 0;
    for (int i = n, j = n - q; j; --i, --j)  {
      diag += a[i][j];
      ipo[i][j] = ipo[i - 1][j] + diag;
    }
  }
  for (int i = 0; i <= k; ++i)  {
    for (int j = 0; i + j <= k; ++j)  {
      d = k - i - j;
      x = col[n - j][i] + lin[n - j + 1][n - j + 1 - d] + ipo[i + d][i + 1];
      if (x > Max)
        Max = x;
    }
  }
  fout << Max;
  return 0;
}