#include<cstdio> #include<algorithm> #include<cstring> #include<queue> typedef long long ll; using namespace std; const int MAXN=505; const ll inf=1e13,INF=1ll<<60; int n,K,a[MAXN][MAXN]; int S,T; namespace Dinic{ const int MAXN=1010,MAXM=6e5; int cnte=1,h[MAXN],to[MAXM],nx[MAXM]; ll ww[MAXM],_ww[MAXM]; inline void adde(int u,int v,ll w){ cnte++; nx[cnte]=h[u]; to[cnte]=v; ww[cnte]=w; h[u]=cnte; } inline void Adde(int u,int v,ll w){ adde(u,v,w); adde(v,u,0); } queue<int> que; int dis[MAXN],cur[MAXN]; bool Bfs(int s,int t){ que.push(s); memset(dis,0,sizeof(dis)); dis[s]=1; while(!que.empty()){ int u=que.front(); que.pop(); for(int i=h[u]; i; i=nx[i]){ int v=to[i]; if(ww[i]&&!dis[v]){ dis[v]=dis[u]+1; que.push(v); } } } memcpy(cur,h,sizeof(h)); return dis[t]; } ll Dfs(int u,int t,ll flw){ if(u==t) return flw; ll res=0; for(int i=cur[u]; i; i=nx[i]){ cur[u]=i; int v=to[i]; if(ww[i]&&dis[v]==dis[u]+1){ ll f=Dfs(v,t,min(flw-res,ww[i])); ww[i]-=f; ww[i^1]+=f; res+=f; if(flw==res) break; } } return res; } ll Flow(int s,int t,ll f){ ll res=0; while(res<f&&Bfs(s,t)) res+=Dfs(s,t,f-res); return res; } ll Calc(){ Flow(S,T,INF); memcpy(_ww,ww,sizeof(ww)); ll res=INF; for(int i=h[S]; i; i=nx[i]){ int v=to[i]; if(v==1) continue; memcpy(ww,_ww,sizeof(ww)); ll sum=ww[i]; Flow(T,v,ww[i^1]); ww[i]=ww[i^1]=0; sum+=Flow(S,T,INF); res=min(res,sum); } return res; } } using Dinic::Adde; int main(){ scanf("%d%d",&n,&K); ll sum=0; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",a[i]+j),sum+=a[i][j]; sum/=2; S=n*2+1; T=n*2+2; for(int i=1; i<=n; i++){ Adde(S,i,inf); if(i>1){ Adde(i+n,T,inf); Adde(i,i+n,INF); } for(int j=1; j<=n; j++) if(i!=j) Adde(i,j+n,a[i][j]*2-K); } printf("%lld\n",sum-Dinic::Calc()); return 0; }