#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MXN = 505; int mat[MXN][MXN]; int N, K; ll ans; void work1() { for (int i(1); i != (1 << N) - 1; ++i) { ll s(0); for (int j(0); j != N; ++j) { for (int k(j + 1); k != N; ++k) { if (static_cast<bool>(i & (1 << j)) ^ static_cast<bool>(i & (1 << k))) s += K - mat[j][k]; else s += mat[j][k]; } } ans = max(ans, s); } cout << ans << endl; } ll getsc(ll i) { ll s(0); for (int j(0); j != N; ++j) { for (int k(j + 1); k != N; ++k) { if (static_cast<bool>(i & (1ll << j)) ^ static_cast<bool>(i & (1ll << k))) s += K - mat[j][k]; else s += mat[j][k]; } } return s; } void work2() { ll ans(0); srand(time(0)); while (clock() < 850) { ll st(rand() % ((1ll << N) - 3) + 1); ll stsc(getsc(st)); ll his(stsc); double temp(10000), rate(0.98), eps(1e-5); while (fabs(temp - eps) > eps) { ll newst(st ^ (1ll << (rand() % N))); if (!newst || newst == (1 << N) - 1) continue; ll newsc(getsc(newst)); his = max(his, newsc); if (newsc > stsc || exp(temp / 10000.0 - 1) > 1.0) { st = newst; stsc = newsc; } temp *= rate; } ans = max(ans, his); } cout << ans << endl; } void work3() { for (int i(0); i != N; ++i) { for (int j(0); j != N; ++j) { cin >> mat[i][j]; if (i > j) ans += mat[i][j]; if (i ^ j) mat[i][j] = mat[i][j] * 2 - K; } } ll ms(0x7f7f7f7f7f7f7f7f); for (int i(0); i != N; ++i) { ll s(0); for (int j(0); j != N; ++j) s += mat[i][j]; ms = min(ms, s); } cout << ans - ms << endl; } int main() { // freopen("sub.in", "r", stdin); // freopen("sub.out", "w", stdout); cin >> N >> K; for (int i(0); i != N; ++i) { for (int j(0); j != N; ++j) { cin >> mat[i][j]; } } if (N <= 12) { work1(); return 0; // } else if (N <= 63) { // work2(); // return 0; } else { work3(); return 0; } return 0; }