#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=6e6;
typedef long long ll;
struct edge
{
int u,v,flo,cap,wei;
};
ll dp[N];
int ed[N];
int a[2003][2003];
const ll inf=1e18;
vector<edge> gp;
vector<int> ma[N];
void addedge(int x,int y,int w)
{
// cout<<x<<' '<<y<<' '<<w<<endl;
ma[x].push_back(gp.size());
gp.push_back({x,y,0,1,w});
ma[y].push_back(gp.size());
gp.push_back({y,x,0,0,-w}); // neg
}
ll flow(int stpl)
{
priority_queue<pair<ll,ll>> pq;
for(int i=0;i<=stpl+1;i++)dp[i]=-inf,ed[i]=-1;
pq.push({0,stpl});
dp[stpl]=0;
while(pq.size()>0)
{
auto it=pq.top();
pq.pop();
ll d=it.first,x=it.second;
if(dp[x]!=d)continue;
// cout<<"a "<<x<<' '<<d<<' '<<dp[x]<<endl;
for(auto id:ma[x])
{
int y=gp[id].v;
// cout<<id<<' '<<gp[id].u<<' '<<gp[id].v<<' '<<gp[id].cap<<endl;
// cout<<y<<' '<<dp[y]<<' '<<d+gp[id].wei<<endl;
if(dp[y]<d+gp[id].wei and gp[id].cap-gp[id].flo>0)
{
ed[y]=id;
dp[y]=d+gp[id].wei;
pq.push({dp[y],y});
}
}
}
int x=stpl+1;
while(ed[x]!=-1)
{
int id=ed[x];
// cout<<x<<' ';
// cout<<id<<' '<<(id^1)<<' '<<gp.size()<<endl;
gp[id].flo++;
gp[id^1].flo--;
// cout<<"using edge "<<gp[id].u<<' '<<gp[id].v<<' '<<gp[id].flo<<' '<<gp[id].cap<<' '<<gp[id].wei<<endl;
x=gp[id].u;
}
// cout<<x<<endl;
// cout<<"ending wiht "<<dp[stpl+1]<<endl;
return dp[stpl+1];
}
int main()
{
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int n,k;
ll tot=0;
cin>>n>>k;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
tot+=a[i][j];
if((i+j)%2==0)
{
addedge(i*n+j,n*n+1,0);
if(j>0)
addedge(i*n+j-1,i*n+j,a[i][j]+a[i][j-1]);
if(j+1<n)
addedge(i*n+j+1,i*n+j,a[i][j]+a[i][j+1]);
if(i>0)
addedge((i-1)*n+j,i*n+j,a[i][j]+a[i-1][j]);
if(i+1<n)
addedge((i+1)*n+j,i*n+j,a[i][j]+a[i+1][j]);
}
if((i+j)%2==1)
{
addedge(n*n,i*n+j,0);
}
}
}
ll fnl=0;
while(k--)
{
fnl+=flow(n*n);
}
cout<<fnl<<endl;
cout<<tot-fnl<<endl;
}
