using namespace std;
#include<fstream>
const int MAX_N = 1007;
int A[MAX_N][MAX_N];
int sol, S, N, K, L;
int dp[MAX_N][MAX_N], diag[MAX_N][MAX_N], up[MAX_N][MAX_N];
inline int ab( int a) { return a>0?a:0; }
int main()
{
	ifstream in("ferma2.in"); ofstream out("ferma2.out");
	in >> N >> K;
	int i, j;
	for(i = 1; i <= N; ++i)
		for(j = 1; j <= i; ++j)
		{
			in >> A[i][j];
			S += A[i][j];
		}
	int minim = S;
	L = N - K;
	for(i = 1; i < L; ++i )
		for( j = 1; j <= i; ++j )
		{
			up[i][j] = up[i-1][j] + A[i][j];
			diag[i][j] = diag[i-1][j-1] + A[i][j];
		}
	int k, ii, jj;
	for(i = L; i <= N; ++i)
	{
		for( j = 1; j <= i; ++j )
		{
			up[i][j] = up[i-1][j] + A[i][j] - A[i-L][j];
			diag[i][j] = diag[i-1][j-1] + A[i][j] - A[i-L][ab(j-L)];
		}
		for(k =1, ii = i - L + 1; ii <= i; ++ii, ++k)
			for(jj = 1; jj <= k; ++jj)
				dp[i][1] += A[ii][jj];
		if( minim > dp[i][1] ) minim = dp[i][1];
		for(j = 2; j + L - 1 <= i; ++j)
		{
			dp[i][j] = dp[i][j-1] - up[i][j-1] + diag[i][j+L-1];
			if( minim > dp[i][j] ) minim = dp[i][j];
		}
	}
	out << S - minim << "\n";
	return 0;
}