N,*T=$<.map{|s|s.split.map &:to_i}
g=->u{$*[u]||=(-2...a=/.$/=~"%b"%u).map{|b|u[b]<1?0:T[a][b]+g[1<<a|1<<b^u]}.max}
p g[2**N[0]-1]