ソースコード
#include<bits/stdc++.h>
using ll = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? 1e9:1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using ld = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
int n;
cin >> n;
vector<vector<int>>d(n+2,vector<int>(n+1,INF));
vector<int>t(n);
erep(e, t) cin >> e;
rep(i,n)rep(j,n)cin >> d[i][j];
vector<int>dp((1<<(n))+1,INF);
dp[0]=0;
for(int s=0; s<(1<<(n));s++){
for(int v=0;v<n;v++){
if(!(s>>v&1)){
int mini=t[v];
for(int u=0; u<n;u++){
if(s>>u&1)cmin(mini,mini - d[v][u]);
}
cmin(dp[s|1<<v],dp[s]+mini);
}
}
}
cout<<dp[(1<<(n))-1]<<endl;
}