#include using namespace std; #define _p(...) (void)printf(__VA_ARGS__) #define forr(x,arr) for(auto&& x:arr) #define _overload3(_1,_2,_3,name,...) name #define _rep2(i,n) _rep3(i,0,n) #define _rep3(i,a,b) for(int i=int(a);i=int(a);i--) #define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__) #define all(x) (x).begin(),(x).end() #define bit(n) (1LL<<(n)) #define sz(x) ((int)(x).size()) #define fst first #define snd second #define _TMPL_OVERLOAD(_1,_2,name,...) name #define _TMPL1(T) template #define _TMPL2(T,U) template #define TMPL(...) _TMPL_OVERLOAD(__VA_ARGS__,_TMPL2,_TMPL1)(__VA_ARGS__) string DBG_DLM(int &i){return(i++==0?"":", ");} #define DBG_B(exp){int i=0;os<<"{";{exp;}os<<"}";return os;} TMPL(T)ostream&operator<<(ostream&os,vectorv); TMPL(T)ostream&operator<<(ostream&os,setv); TMPL(T)ostream&operator<<(ostream&os,queueq); TMPL(T)ostream&operator<<(ostream&os,priority_queueq); TMPL(T,K)ostream&operator<<(ostream&os,pairp); TMPL(T,K)ostream&operator<<(ostream&os,mapmp); TMPL(T,K)ostream&operator<<(ostream&os,unordered_mapmp); templatevoid DBG(ostream&os,TPL t){} templatevoid DBG(ostream&os,TPL t){os<<(I==0?"":", ")<(t);DBG(os,t);} TMPL(T,K)void DBG(ostream&os,pairp,string delim){os<<"("<t){os<<"(";DBG<0,tuple,Ts...>(os,t);os<<")";return os;} TMPL(T,K)ostream&operator<<(ostream&os,pairp){DBG(os,p,", ");return os;} TMPL(T)ostream&operator<<(ostream&os,vectorv){DBG_B(forr(t,v){os<s){DBG_B(forr(t,s){os<q){DBG_B(for(;q.size();q.pop()){os<q){DBG_B(for(;q.size();q.pop()){os<m){DBG_B(forr(p,m){os<");});} TMPL(T,K)ostream&operator<<(ostream&os,unordered_mapm){DBG_B(forr(p,m){os<");});} #define DBG_OVERLOAD(_1,_2,_3,_4,_5,_6,macro_name,...)macro_name #define DBG_LINE(){char s[99];sprintf(s,"line:%3d | ",__LINE__);cerr<>(istream&is,pair&p){is>>p.fst;is>>p.snd;return is;} TMPL(T)istream&operator>>(istream&is,vector&v){forr(e,v)is>>e;return is;} #define rea(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__); TMPL(T)void MACRO_VAR_Scan(T&t){cin>>t;} TMPL(H,...Ts)void MACRO_VAR_Scan(H&h,Ts&...ts) {cin>>h;MACRO_VAR_Scan(ts...);} #define rea_vecs(type,n,...)vector __VA_ARGS__;MACRO_VEC_ROW_Init(n,__VA_ARGS__);rep(i,n)MACRO_VEC_ROW_Scan(i,__VA_ARGS__); TMPL(T)void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); } TMPL(H,...Ts)void MACRO_VEC_ROW_Init(int n,H&h,Ts&...ts){h.resize(n);MACRO_VEC_ROW_Init(n,ts...);} TMPL(T)void MACRO_VEC_ROW_Scan(int p,T&t){cin>>t[p];} TMPL(H,...Ts)void MACRO_VEC_ROW_Scan(int p,H&h,Ts&...ts){cin>>h[p];MACRO_VEC_ROW_Scan(p,ts...);} #define rea_vec(type,n,c) vectorc(n);cin>>c; //#define int long long // consider risk of MLE using ll=long long; using pii=pair;using pll=pair;using pil=pair;using pli=pair; using vs=vector;using vvs=vector;using vvvs=vector; using vb=vector;using vvb=vector;using vvvb=vector; using vi=vector;using vvi=vector;using vvvi=vector; using vl=vector;using vvl=vector;using vvvl=vector; using vd=vector;using vvd=vector;using vvvd=vector; using vpii=vector;using vvpii=vector;using vvvpii=vector; templatebool amax(T&a,T&b){return abool amin(T&a,T&b){return a>b?a=b,1:0;} ll ri(){ll l;cin>>l;return l;} string rs(){string s;cin>>s;return s;} templateT read(){T t;cin>>t;return t;} class Dinic { const int INF = 2e9; // 行き先、容量、逆辺のインデックス struct edge { int to, cap, rev; }; public: int V; vector> G; vector level, iter; Dinic(int V) : V(V), G(V), level(V), iter(V) {} // fromからtoへ向かう容量capの辺をグラフに追加する void add_edge(int from, int to, int cap) { G[from].push_back((edge){to, cap, (int) G[to].size()}); G[to].push_back((edge){from, 0, (int) G[from].size() - 1}); } private: // sからの最短距離をBFSで算する void bfs(int s) { fill(level.begin(), level.end(), -1); level[s] = 0; queue q; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); for (int i = 0; i < (int) G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } } // 増加パスをDFSで探す int dfs(int v, int t, int f) { if (v == t) return f; for (int &i = iter[v]; i < (int) G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } public: // sからtへの最大流を求める int max_flow(int s, int t) { int flow = 0; for (;;) { bfs(s); if (level[t] < 0) return flow; fill(iter.begin(), iter.end(), 0); int f; while ((f = dfs(s, t, INF)) > 0) { flow += f; } } } }; ll solve() { rea(int, n); vvi A(n, vi(n)); rep(i, n) { rep(j, n) { A[i][j] = ri(); } } // bitdp... vi dp(bit(n)); rep(i, bit(n)) { rep(j, n) if ((i & bit(j)) == 0) { rep(k, j+1, n) if ((i & bit(k)) == 0) { dp[i | bit(j) | bit(k)] = max(dp[i | bit(j) | bit(k)], dp[i] + A[j][k]); } } } return dp[bit(n)-1]; } void Main() { cout << solve() << endl; } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); Main(); return 0; }