#include <bits/stdc++.h> using namespace std; const int N = 1005; int n, k, in, h[N], chose[N], ans, vis[N], w[N][N], cnt; bool tong[N]; struct ab { int v, w, nxt; }mp[N * N]; void add(int x, int y, int z) { mp[++cnt].v = y; mp[cnt].w = z; mp[cnt].nxt = h[x]; h[x] = cnt; } void dfs(int u, int fa, int val, int cnt) { if(tong[u > n ? u - n : u + n]) return; if(cnt == n) { int tmp = 0; for(int i = 1; i <= n; i++) { if(chose[i] > n) tmp++; else tmp--; } if(tmp == n or tmp == -n) return; for(int i = h[u]; i; i = mp[i].nxt) { int v = mp[i].v; if(v == fa) continue; if(tong[v]) { val += mp[i].w; } } // printf("%d ", val); ans = max(ans, val); // for(int i = 1; i <= n; i++) // { // printf("%d ", chose[i]); // } // printf("\n"); } for(int i = h[u]; i; i = mp[i].nxt) { int v = mp[i].v; if(v == fa) continue; if(tong[v]) { val += mp[i].w; } } // if(vis[u] > val) return; // vis[u] = val; for(int i = h[u]; i; i = mp[i].nxt) { int v = mp[i].v; if(tong[v]) continue; tong[v] = 1; chose[cnt + 1] = v; dfs(v, u, val + mp[i].w, cnt + 1); tong[v] = 0; } } int main () { scanf("%d%d", &n, &k); if(k == 1) { printf("%d\n", n - 1); return 0; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf("%d", &in); w[i][j] = in; } } for(int i = 1; i <= n << 1; i++) { for(int j = 1; j <= n << 1; j++) { if(i == j) continue; if(i <= n and j <= n) add(i, j, w[i][j]); if((i > n and j <= n) or (i <= n and j > n)) add(i, j, k - w[i > n ? i - n : i][j > n ? j - n : j]); if(i > n and j > n) add(i, j, w[i - n][j - n]); } } add(0, 1, 0); add(0, 1 + n, 0); dfs(0, 0, 0, 0); printf("%d", ans); return 0; }