#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-ffast-math") #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<ctime> #include<cstdlib> typedef long long ll; using namespace std; const int MAXN=505,INF=0x7fffffff; int n,K,a[MAXN][MAXN]; long clk; namespace Dinic{ const int MAXN=505,MAXM=5e5; int cnte=1,h[MAXN],to[MAXM],nx[MAXM]; int ww[MAXM],_ww[MAXM]; inline void adde(int u,int v,int w){ cnte++; nx[cnte]=h[u]; to[cnte]=v; ww[cnte]=w; h[u]=cnte; } inline void Adde(int u,int v,int 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]; } int Dfs(int u,int s,int flw){ if(u==s) return flw; int res=0; for(int i=cur[u]; i; i=nx[i]){ cur[u]=i; int v=to[i]; if(ww[i^1]&&dis[u]==dis[v]+1){ int f=Dfs(v,s,min(flw-res,ww[i^1])); ww[i^1]-=f; ww[i]+=f; res+=f; if(flw==res) break; } } return res; } int Flow(int s,int t){ //clk-=clock(); int res=0; while(Bfs(s,t)) res+=Dfs(t,s,INF); //clk+=clock(); return res; } int Calc(){ memcpy(_ww,ww,sizeof(ww)); if(n==1) return 0; int res=INF; for(int i=1; i<=n; i++){ int sum=0; for(int j=1; j<=n; j++) if(i!=j) sum+=a[i][j]*2-K; res=min(res,sum); } int tot=70; while(tot--){ int u=rand()%n+1,v=rand()%n+1; if(u==v) continue; memcpy(ww,_ww,sizeof(ww)); res=min(res,Flow(u,v)); } 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; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(i!=j) Adde(i,j,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; }