ソースコード
#line 1 "playspace/main.cpp"
#include <bits/stdc++.h>
#line 8 "library/gandalfr/other/io_supporter.hpp"
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++)
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &st) {
for (const T &x : st) {
std::cout << x << " ";
}
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::multiset<T> &st) {
for (const T &x : st) {
std::cout << x << " ";
}
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::deque<T> &dq) {
for (const T &x : dq) {
std::cout << x << " ";
}
return os;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
os << p.first << ' ' << p.second;
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, std::queue<T> &q) {
int sz = q.size();
while (--sz) {
os << q.front() << ' ';
q.push(q.front());
q.pop();
}
os << q.front();
q.push(q.front());
q.pop();
return os;
}
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
for (T &in : v)
is >> in;
return is;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
#line 3 "playspace/main.cpp"
using namespace std;
using ll = long long;
const int INF = 1001001001;
const ll INFLL = 1001001001001001001;
const ll MOD = 1000000007;
const ll _MOD = 998244353;
#define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++)
#define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--)
#define all(a) (a).begin(),(a).end()
#define debug(a) std::cerr << #a << ": " << a << std::endl
#define LF cout << endl
#ifdef ENABLE_MULTI_FOR
#define mrep(it, mr) for(multi_iter it(mr); !it.fin(); ++it)
#endif
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
void Yes(bool ok){ std::cout << (ok ? "Yes" : "No") << std::endl; }
int main() {
int N;
cin >> N;
vector<int> T(N);
cin >> T;
vector<vector<int>> A(N, vector<int>(N, INF));
cin >> A;
vector<int> dp(1 << N, INF);
rep(i,0,N) dp[0] = 0;
rep(S,0,1<<N) {
rep(i,0,N) {
if (!(S >> i & 1)) {
int sum = 0;
rep(j,0,N) {
if (S >> j & 1) {
sum += A[j][i];
}
}
chmin(dp[S | (1 << i)], dp[S] + T[i] - sum);
}
}
}
cout << dp[(1 << N) - 1] << endl;
}