Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 1010

int A[MAXN];

int E[MAXN][MAXN];

struct edge

{

	int to,nxt,f;

}e[(MAXN * MAXN + MAXN * 2) * 2];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b,int f)

{

	e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

	return;

}

typedef long long ll;

int ch[MAXN];

int s,t;

bool BFS()

{

	queue<int> q;q.push(s);

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

ll flow(int k,ll f)

{

	if(k == t)return f;

	ll r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(1ll * e[i].f,f - r));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

		lin[k] = i;

	}

	if(r == 0)ch[k] = -1;

	return r;

}

#define INF 0x3f3f3f3f3f3f3f3f

int cur[MAXN];

ll dinic()

{

	ll ans = 0,r;

	memcpy(cur,lin,sizeof(cur));

	while(BFS())

	{

		ans += flow(s,INF);

		memcpy(lin,cur,sizeof(cur));

	}

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)A[i] = rd();

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)E[i][j] = rd();

	s = n + 1;t = s + 1;

	ll ans = 0;

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)ans += E[i][j];

	for(int i = 1;i <= n;++i)

	{

		int sum = 0;

		for(int j = 1;j <= n;++j)sum += E[i][j];

		add(s,i,sum - E[i][i]);

		add(i,t,A[i]);

	}

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)add(i,j,E[i][j] + E[j][i]);

	cout << ans - dinic() << endl;

	return 0;

}