{利用计算最佳连通分支算法即可求得}
program miner;
const
maxv=20;
var
link,longlink:array[1..maxv,1..maxv] of boolean;
a:array[1..maxv,1..maxv] of 0..1;
f:array[1..maxv] of boolean;
w:array[1..maxv] of integer;
v,e,k,i,j,s,max,maxk:integer;
procedure init;
begin
assign(input,'miner.in');
reset(input);
assign(output,'miner.out');
rewrite(output);
fillchar(longlink,sizeof(longlink),false);
fillchar(link,sizeof(link),false);
readln(v);
for i:=1 to v do
read(w[i]);
readln;
for i:=1 to v do
begin
for j:=i+1 to v do
begin
read(a[i,j]);
if a[i,j]=1
then begin
link[i,j]:=true;
link[j,i]:=true;
end;
end;{for j}
readln;
end;{for i}
for i:=1 to v do begin
for j:=1 to v do
write(link[i,j]:6);
writeln;end;
end;{init}
procedure bibao;
begin
longlink:=link;
for k:=1 to v do
for i:=1 to v do
for j:=1 to v do
longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]);
end;{bibao}
procedure dfs(i:integer);
begin
write(i,' ');
f[i]:=true;
for j:=1 to v do
if (not f[j]) and longlink[i,j]
then dfs(j);
end;{dfs}
begin{main}
init;
bibao;
max:=0;
for i:=1 to v do
begin
s:=0;
for j:=1 to v do
if longlink[i,j]
then s:=s+w[j];
if s>max
then begin
max:=s;
maxk:=i;
end;
end;
fillchar(f,sizeof(f),false);
dfs(maxk);
writeln;
write(max);
close(input);
close(output);
end.
//delphi/7192