ソースコード
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;
int t[20], a[20][20], memo[1000000];
int n;
int dfs(int p, int bit, int res){
if(p == n)return res;
int mn = INF;
if(memo[bit] != -1)return res+memo[bit];
rep(i,n){
int tmp = t[i];
if((bit >> i) & 1)continue;
rep(j,n){if((bit >> j) & 1)tmp -= a[j][i];}
int tt = dfs(p+1, (bit | (1<<i)), tmp);
chmin(mn, tt);
}
memo[bit] = mn;
return res+mn;
}
signed main(){
fill(memo, memo+1000000, -1);
scanf("%lld", &n);
rep(i,n)scanf("%lld", &t[i]);
rep(i,n)rep(j,n)scanf("%lld", &a[i][j]);
int res = dfs(0, 0, 0);
printf("%lld\n", res);
return 0;
}