#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair

using namespace std;

const string name = "ferma2",
             in_file = name + ".in",
             out_file = name + ".out";

ifstream fin(in_file);
ofstream fout(out_file);

const int MAX = 1e3 + 5;

int n, k;
int triangle[MAX][MAX];
int sum_line[MAX][MAX], sum_diag[MAX][MAX];
int dp[MAX][MAX];
int sum_total;

int compute_first(int x, int y, int length) {
	int sum = 0;
	for (int i = 0; i < length; i++) {
		for (int j = 0; j < length - i; j++) {
			sum += triangle[x - i][y + j];
		}
	}
	return sum;
}

int main() {
	fin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			fin >> triangle[i][j];
			sum_total += triangle[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			sum_line[i][j] = triangle[i][j] + sum_line[i][j - 1];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n - i + 1; j++) {
			sum_diag[i][j] = triangle[i + j - 1][j] + sum_diag[i][j - 1];
		}
	}

	int length_triangle = n - k;
	if (!length_triangle) {
		fout << sum_total;
		return 0;
	}

	for (int j = 1; j <= n; j++) {
		int current_line = length_triangle + j - 1;
		if (current_line < 0 || current_line > n) {
			break;
		}

		dp[current_line][j] = compute_first(current_line, j, length_triangle);
		for (int i = current_line + 1; i <= n; i++) {
			dp[i][j] = dp[i - 1][j] +
			    sum_line[i][j + length_triangle - 1] - sum_line[i][j - 1] -
			    sum_diag[i - current_line][j + length_triangle - 1] + sum_diag[i - current_line][j - 1];
		}
	}

	int minn = sum_total;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j]) {
				minn = min(minn, dp[i][j]);
			}
		}
	}

	fout << sum_total - minn;

	return 0;
}