#include<cstdio>
#include<string>
#include<queue>
#include<cstring>
#define R register int
#define N 1005
#define ll long long
#define inf 12345678910
using namespace std;
struct G{int to,next;ll f;}e[N*N];
int n,head[N],en,cur[N],dep[N],cnt;
ll a[N],b[N][N],sum1[N],sum;
int max(int a,int b) {return a>b?a:b;}
int min(int a,int b) {return a<b?a:b;}
void read(int &x)
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
void read1(ll &x)
{
	x=0;ll f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
void add(int u,int v,int flow)
{
	e[++cnt].to=v;e[cnt].f=flow;
	e[cnt].next=head[u];head[u]=cnt;
}
bool bfs()
{
	for (R i=1;i<=en;++i)
		dep[i]=-1;
	queue<int>q;q.push(0);dep[0]=0;
	while (!q.empty())
	{
		int u=q.front();q.pop();
		for (R i=head[u];i!=-1;i=e[i].next)
		{
			int v=e[i].to;
			if (dep[v]==-1 && e[i].f) dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[en]!=-1;
}
ll dfs(int u,ll maxflow)
{
	ll tot=0;if (u==en) return maxflow;
	for (R i=cur[u];i!=-1;i=e[i].next)
	{
		cur[u]=e[i].next;int v=e[i].to;
		if (dep[v]==dep[u]+1 && e[i].f)
		{
			ll ok=dfs(v,min(maxflow-tot,e[i].f));
			e[i].f-=ok;e[i^1].f+=ok;tot+=ok;if (tot==maxflow) break;
		}
	}
	return tot;
}
ll dinic()
{
	ll ans=0;
	while (bfs())
	{
		for (R i=0;i<=en;++i)
			cur[i]=head[i];
		ans+=dfs(0,inf);
	}
	return ans;
}
int main()
{
	read(n);cnt=-1;memset(head,-1,sizeof(head));en=n+1;
	for (R i=1;i<=n;++i)
		read1(a[i]),add(i,en,a[i]),add(en,i,0);
	for (R i=1;i<=n;++i)
		for (R j=1;j<=n;++j)
		{
			read1(b[i][j]);
			if (i!=j)
			{
				add(i,j,b[i][j]<<1);add(j,i,0);
				sum1[i]+=b[i][j];sum+=b[i][j];
			}
		}
	for (R i=1;i<=n;++i)
		add(0,i,sum1[i]),add(i,0,0);
	printf("%lld\n",sum-dinic());
	return 0;
}