ソースコード
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
for (auto &i : v) is >> i;
return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
const string delimiter = "\n";
REP(i, v.size())
{
os << v[i];
if (i != v.size() - 1) os << delimiter;
}
return os;
}
/*--------------------template--------------------*/
int n;
vi t;
vector<vi> a;
int dp[1 << 16];
int solve(int bit)
{
if (bit == (1 << n) - 1) return 0;
if (dp[bit] >= 0) return dp[bit];
int res = 1e9;
REP(i, n)
{
if ((bit >> i) & 1) continue;
int x = 0;
REP(j, n)
{
if ((bit >> j) & 1) x += a[j][i];
}
chmin(res, solve(bit | (1 << i)) + t[i] - max(0, x));
}
return dp[bit] = res;
}
int main()
{
cin.sync_with_stdio(false); cout << fixed << setprecision(10);
MS(dp, -1);
cin >> n;
t.resize(n); cin >> t;
a.resize(n, vi(n)); cin >> a;
cout << solve(0) << endl;
return 0;
}