#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<ctime> #include<random> #include<chrono> #include<cstdlib> typedef long long ll; using namespace std; //mt19937 rnd(chrono::system_clock::now().time_since_epoch().count()); const int MAXN=505; const ll inf=1e13,INF=1ll<<60; int n,K,a[MAXN][MAXN]; int S,T; long clk; 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){ //clk-=clock(); ll res=0; while(res<f&&Bfs(s,t)) res+=Dfs(s,t,f-res); //clk+=clock(); 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; if((rand()&31)==0){ 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); }else{ ll sum=0; for(int k=1; k<=n; k++) if(k!=v) sum+=a[k][v]*2-K; res=min(res,sum); } } return res; } } using Dinic::Adde; int main(){ srand(time(NULL)); //freopen("in","r",stdin); 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()); //printf("%.2f\n",(double)(clock())/CLOCKS_PER_SEC); //printf("%.2f\n",(double)(clk)/CLOCKS_PER_SEC); return 0; }