#include <fstream>

using namespace std;

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

int N , K , dp[2][1005][1005] , s[3][1005][1005];

int main()
{
	int ans = 0 , L = 0 , val;
	fin>>N>>K;
	for(int i = 1;i <= N;++i) {
		for(int j = 1;j <= i;++j){
			fin>>val;
			s[0][i][j] = s[0][i][j - 1] + val;
			s[1][i][j] = s[1][i - 1][j] + val;
			s[2][i][j] = s[2][i - 1][j - 1] + val;
		}
	}
	for(int k = 1;k <= K;++k,L = 1 - L) {
		for(int i = 0;i <= N && i <= K;i++) {
			for(int j = 0;j <= N && i + j <= K;j++) {
				int lastDim = N - k + 1;
				int x = i + 1;
				int y = j + 1;
				dp[1 - L][x][y] = 0;
				dp[1 - L][x][y] = max(dp[1 - L][x][y], dp[L][x - 1][y] + s[2][x - 1 + lastDim - 1][y + lastDim - 1] - s[2][x - 2][y - 1]);
				dp[1 - L][x][y] = max(dp[1 - L][x][y], dp[L][x][y - 1] + s[1][x + lastDim - 1][y - 1] - s[1][x  - 1][y - 1]);
				dp[1 - L][x][y] = max(dp[1 - L][x][y], dp[L][x][y] + s[0][x + lastDim - 1][y + lastDim - 1] - s[0][x + lastDim - 1][y - 1]);
				ans = max(ans,dp[1 - L][x][y]);
			}
		}
	}
	fout<<ans;
	return 0;
}