#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> // #include<atcoder/scc> using namespace std; // using namespace atcoder; void chmax(int &a, int b){ if(a < b) a = b; } void solve(){ int n; cin >> n; vector<vector<int>> F(n, vector<int>(n)); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> F[i][j]; vector<int> dp(1 << n); int S; for(int bit = 0; bit < (1 << n - 1) - 1; bit++){ bool pc = 0; int ii; for(int i = 0; i < n - 1; i++){ if(bit >> i & 1) pc ^= 1; else if(ii == -1){ ii = i; } } S = bit; if(pc) S |= pc << (n - 1); for(int i = 0; i < n; i++){ if(S & 1); else{ chmax(dp[S | (1 << i) | (1 << ii)], dp[S] + F[i][ii]); } S >>= 1; } } cout << dp[(1 << n) - 1] << "\n"; } int main(){ cin.tie(0)->sync_with_stdio(0); int t; t = 1; // cin >> t; while(t--) solve(); }