#include <bits/stdc++.h> #include <bits/extc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define For(i,s,t) for (int i = (s); i <= (t); ++i) #define Rof(i,s,t) for (int i = (s); i >= (t); --i) using LL = long long; using Pii = pair<int, int>; template <typename T> using Heap = __gnu_pbds::priority_queue<T, greater<T>, __gnu_pbds::pairing_heap_tag>; template <typename T> using BST = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; const int inf = 0x3f3f3f3f; const LL infLL = 0x3f3f3f3f3f3f3f3fLL; const int maxn = 500 + 5; class StoerWagner { int n, s, t; int w[maxn][maxn]; LL dis[maxn]; bool vis[maxn], mrk[maxn]; LL cut(int c) { LL ret; memset(dis, 0, sizeof(dis)); memset(vis, false, sizeof(vis)); while (c--) { int u = -1; rep(v,n) if (!mrk[v] && !vis[v] && (u == -1 || dis[v] > dis[u])) u = v; vis[u] = true, ret = dis[u], s = t, t = u; rep(v,n) if (!mrk[v] && !vis[v]) dis[v] += w[u][v]; } return ret; } public: void init(int n) { this->n = n; memset(w, 0, sizeof(w)); } void add_edge(int u, int v, int w = 1) { this->w[u][v] += w; } LL min_cut() { LL ret = infLL; memset(mrk, false, sizeof(mrk)); rep(i,n-1) { ret = min(ret, cut(n - i)); mrk[t] = true; rep(u,n) if (!mrk[u]) w[s][u] += w[t][u], w[u][s] += w[u][t]; } return ret; } } grp; struct CostMaximizer { long long maxPossible(int N, int K, vector <int> w) { grp.init(N); LL ret = 0; int k = 0; For(i,1,N) For(j,i+1,N) { grp.add_edge(i - 1, j - 1, 2 * w[k] - K); grp.add_edge(j - 1, i - 1, 2 * w[k] - K); ret += w[k++]; } return ret - grp.min_cut(); } }; int main() { // freopen("sub.in", "r", stdin); //freopen("sub.out", "w", stdout); int n, k; scanf("%d%d", &n, &k); vector<int> w; For(i,1,n) For(j,1,n) { int x; scanf("%d", &x); if (j > i) w.push_back(x); } printf("%lld\n", (new CostMaximizer())->maxPossible(n, k, w)); return 0; }