ソースコード
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#include<bitset>
#define int long long
#define ll long long
#define mod 1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
double pi = 3.141592653589793;
using namespace std;
//ここから始めよう
int dp[1<<20];//この集合のときの最小値
int n;int a[20];
int t[20][20];
int sum(int bit,int j){
int s=0;
rep(i,0,n){
if(bit&1<<i)s+=t[i][j];
}return s;
}
int z=0;
int solve(int bit){
int res=dp[bit];
if(~res)return res;
res=inf;
if(bit==0)return 0;
rep(i,0,n){
if(!(bit&1<<i))continue;
res=min(res,solve(bit & ~(1<<i))+max(z,a[i]-sum(bit & ~(1<<i),i)));
}
dp[bit]=res;
// cout<<res<<" "<<bit<<endl;
return dp[bit];
}
signed main(){
cin>>n;
rep(i,0,n)cin>>a[i];
rep(i,0,n)rep(j,0,n)cin>>t[i][j];
memset(dp,-1,1<<18);
cout<<solve((1<<n)-1)<<endl;return 0;
}