#include<cstdio> #include<algorithm> #include<ctype.h> #include<cstring> #include<iostream> #include<vector> #include<queue> #include<ctime> #include<cmath> #include<queue> #include<map> #include<set> #include<unordered_map> #include<stack> #define pr pair<int,int> #define eps 1e-8 #define db double #define int long long using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-')f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x*f; } int dis[605][605],n,k,s,t,ans; int awa[605],num[605]; bool viss[605],vis[605]; void work(int x) { memset(vis,0,sizeof(vis)); memset(awa,0,sizeof(awa)); for(int i=1; i<=n-x+1; i++) { int id=0; for(int j=1; j<=n; j++) if(!vis[j]&&!viss[j]&&(awa[j]>awa[id]||!id)) id=j; num[i]=id,vis[id]=1; for(int j=1; j<=n; j++) if(!vis[j]&&!viss[j]) awa[j]+=dis[id][j]; } s=num[n-x],t=num[n-x+1]; ans=min(ans,awa[t]); } int a[605][605]; signed main() { n=read(),k=read(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dis[i][j]=read(); int cnt=0; for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) cnt+=dis[i][j]; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(i!=j) dis[i][j]=2*dis[i][j]-k; ans=0x3f3f3f3f3f3f3f3fLL; for(int i=1; i<n; i++) { work(i); viss[t]=1; for(int j=1; j<=n; j++) if(!viss[j]) dis[s][j]+=dis[t][j],dis[j][s]+=dis[j][t]; } printf("%lld\n",cnt-ans); return 0; }