#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN=610,INF=1e9; int n,m,x,y,z,s,t,dis[MAXN][MAXN],w[MAXN],dap[MAXN],vis[MAXN],ord[MAXN]; int proc (int x) { memset(vis,0,sizeof(vis)); memset(w,0,sizeof(w)); w[0]=-1; for (int i=1; i<=n-x+1; i++) { int mx=0; for (int j=1; j<=n; j++) { if (!dap[j]&&!vis[j]&&w[j]>w[mx]) { mx=j; } } vis[mx]=1,ord[i]=mx; for (int j=1; j<=n; j++) { if (!dap[j]&&!vis[j]) { w[j]+=dis[mx][j]; } } } s=ord[n-x],t=ord[n-x+1]; return w[t]; } int sw () { int res=INF; for (int i=1; i<n; i++) { res=min(res,proc(i)); dap[t]=1; for (int j=1; j<=n; j++) { dis[s][j]+=dis[t][j]; dis[j][s]+=dis[j][t]; } } return res; } int a[505][505]; signed main () { scanf("%lld%lld",&n,&m); int ans=0; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%lld",&a[i][j]); for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) dis[i][j]=dis[j][i]=2*a[i][j]-m,ans+=a[i][j]; printf("%lld\n",ans-sw()); return 0; }