比较明显的网络流最小割模型，对于这种模型我们需要先求获利的和，然后减去代价即可。
我们对于第i个人来说， 如果选他，会耗费A[I]的代价，那么(source,i,a[i])代表选他之后的代价，如果不选他，我们会产生Σw[i][j] 1<=j<=n的代价，也就是这么多的利益我们无法得到，然后对于两个人的互相影响，连边(i,j,2*w[i][j])，代表如果不选i，选j的话，本来i中选j的利益得不到，又要损失j对i的影响为w[i][j]。所以共计损失2*w[i][j]。之后求最小割=最大流就行了。
/**************************************************************
Problem: 2039
User: BLADEVIL
Language: Pascal
Result: Accepted
Time:860 ms
Memory:47112 kb
****************************************************************/
//By BLADEVIL
var
n :longint;
pre, other, len :array[0..4000010] of longint;
last :array[0..1010] of longint;
l :longint;
source, sink :longint;
que, d :array[0..1010] of longint;
ans :longint;
function min(a,b:longint):longint;
begin
if a>b then min:=b else min:=a;
end;
procedure connect(x,y,z:longint);
begin
inc(l);
pre[l]:=last[x];
last[x]:=l;
other[l]:=y;
len[l]:=z;
end;
procedure init;
var
i, j :longint;
x :longint;
sum :longint;
begin
read(n);
source:=n+2; sink:=source+1; l:=1;
for i:=1 to n do
begin
read(x);
connect(source,i,x);
connect(i,source,0);
end;
for i:=1 to n do
begin
sum:=0;
for j:=1 to n do
begin
read(x);
if x=0 then continue;
sum:=sum+x;
connect(i,j,x<<1);
connect(j,i,0);
ans:=ans+x;
end;
connect(i,sink,sum);
connect(sink,i,0);
end;
end;
function bfs:boolean;
var
h, t, cur :longint;
q, p :longint;
begin
fillchar(d,sizeof(d),0);
h:=0; t:=1;
que[1]:=source;
d[source]:=1;
while h<t do
begin
inc(h);
cur:=que[h];
q:=last[cur];
while q<>0 do
begin
p:=other[q];
if (len[q]>0) and (d[p]=0) then
begin
inc(t);
que[t]:=p;
d[p]:=d[cur]+1;
if p=sink then exit(true);
end;
q:=pre[q];
end;
end;
exit(false);
end;
function dinic(x,flow:longint):longint;
var
rest, tmp :longint;
q, p :longint;
begin
if x=sink then exit(flow);
rest:=flow;
q:=last[x];
while q<>0 do
begin
p:=other[q];
if (len[q]>0) and (d[p]=d[x]+1) and (rest>0) then
begin
tmp:=dinic(p,min(len[q],rest));
dec(rest,tmp);
dec(len[q],tmp);
inc(len[q xor 1],tmp);
end;
q:=pre[q];
end;
exit(flow-rest);
end;
procedure main;
begin
while bfs do ans:=ans-dinic(source,maxlongint div 10);
writeln(ans);
end;
begin
init;
main;
end.