# ソースコード

```
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <typeinfo>
#include <utility>
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;
void chmin(int &a,int b) {
if (a == -1)a = b;
else if (a > b)a = b;
return;
}
int n, t[16], a[16][16], dp[1 << 16];
int main() {
cin >> n;
rep(i, 0, n)cin >> t[i];
rep(i, 0, n)rep(j, 0, n)cin >> a[i][j];
rep(msk, 0, 1 << n)dp[msk] = -1;
dp[0] = 0;
rep(msk, 0, 1 << n)rep(u, 0, n)if(!((1<<u)&(msk)) && dp[msk] >= 0){
int T = t[u];
rep(j, 0, n)if ((1 << j)&msk)T -= a[j][u];
chmin(dp[msk+(1<<u)],dp[msk]+T);
}
cout << dp[(1<<n)-1] << endl;
return 0;
}
```