ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount
#define INF INT_MAX/3
#define mod 1000000007
int n;
int t[16];
int a[16][16];
int dp[1<<16];
int main(){
cin>>n;
rep(i,n)cin>>t[i];
rep(i,n)rep(j,n)cin>>a[i][j];
rep(i,1<<n)dp[i]=INF;
dp[0]=0;
rep(S,1<<n){
rep(i,n){
if((S>>i)&1)continue;
int tot=t[i];
rep(j,n){
if((S>>j)&1)tot-=a[j][i];
}
minch(dp[S^(1<<i)],dp[S]+tot);
}
}
cout<<dp[(1<<n)-1]<<endl;
return 0;
}