#include<bits/stdc++.h> #define I using #define love namespace #define Elaina std #define ll long long I love Elaina; const int N=1000010; const int M=5000010; ll read(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); } return x*f; } ll n,k,w[510][510],tot,sum,ans; namespace AyaseEli{ ll S,T,head[N],cnt=1,dep[N]; struct edge{ ll to,nxt,flow; }e[M]; void add(int u,int v,ll f){ e[++cnt].to=v,e[cnt].nxt=head[u],e[cnt].flow=f,head[u]=cnt; e[++cnt].to=u,e[cnt].nxt=head[v],e[cnt].flow=0,head[v]=cnt; } bool bfs(){ memset(dep,-1,sizeof(dep)); queue<int>q; q.push(S); dep[S]=0; while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(dep[v]==-1&&e[i].flow>0){ dep[v]=dep[u]+1; q.push(v); } } } return dep[T]!=-1; } ll dfs(int u,ll cur){ if(u==T||!cur)return cur; ll sum=0,tmp; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(e[i].flow>0&&dep[u]+1==dep[v]){ tmp=dfs(v,min(cur-sum,e[i].flow)); if(!tmp)dep[v]=-1; e[i].flow-=tmp,e[i^1].flow+=tmp,sum+=tmp; if(sum==cur)break; } } return sum; } ll Dinic(){ ll maxflow=0; while(bfs())maxflow+=dfs(S,1e18); return maxflow; } } I love AyaseEli; int main(){ n=read(),k=read(); S=0,T=n+1; ll ss=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ w[i][j]=read(); if(!w[i][j])continue; sum+=3*w[i][j]-k; } } sum/=2; for(int cur=2;cur<=n;cur++){ cnt=1,tot=T; memset(head,0,sizeof(head)); add(S,1,1e18),add(cur,T,1e18); for(int i=1;i<=n;i++){ for(int j=1;j<i;j++){ add(S,++tot,2*w[i][j]-k),add(tot,i,1e18),add(tot,j,1e18); add(++tot,T,2*w[i][j]-k),add(i,tot,1e18),add(j,tot,1e18); } } ans=max(ans,sum-Dinic()); } printf("%lld",ans); return 0; }