记录编号	7861	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 埃雷萨拉斯的宝藏	最终得分	100
用户昵称	thegy	是否通过	通过
代码语言	Pascal	运行时间	0.668 s
提交时间	2008-11-11 21:46:33	内存使用	53.83 MiB

program eldrethalas;
type
  node=record
         num:longint;
         adj:array[1..2500]of longint;
         long:array[1..2500]of longint;
       end;
var
  fin,fout:text;
  n,p,h0:longint;
  h:array[1..2500]of longint;
  i,j,k,k1,k2,q:longint;
  v:array[0..2501]of node;
  hash:array[0..2501]of boolean;
  g:array[1..50,1..50]of longint;
  gb:array[1..2500,1..2500]of boolean;
  ans:longint;
  ax,ay:array[1..4]of longint;

procedure Dijsktra;
var
  i,j,v0,min:longint;
  dis:array[0..2501]of longint;
  visit:array[0..2501]of boolean;
  flag:boolean;
procedure RELAX(x,y,z:longint);
begin
  if dis[y]>dis[x]+z then dis[y]:=dis[x]+z;
end;
begin
  dis[0]:=0;
  for i:=1 to p+1 do dis[i]:=maxlongint;
  for i:=0 to p+1 do visit[i]:=false;
  for i:=0 to p+1 do begin
    min:=maxlongint;
    for j:=0 to p+1 do
      if not(visit[j]) then
        if dis[j]<min then begin
          min:=dis[j];
          v0:=j;
        end;
    visit[v0]:=true;
    for k:=1 to v[v0].num do
      RELAX(v0,v[v0].adj[k],v[v0].long[k]);
  end;
  ans:=dis[p+1];
end;
function hf(x,y:longint):boolean;
begin
  if (0<x) and (x<=n) and (0<y) and (y<=n) then hf:=true else hf:=false;
end;
begin
  assign(fin,'eldrethalas.in'); reset(fin);
  assign(fout,'eldrethalas.out'); rewrite(fout);
  read(fin,n,p,h0);
  for i:=1 to p do read(fin,h[i]);
  for k1:=1 to n do
    for k2:=1 to n do
      read(fin,g[k1,k2]);
//**********************************************
  ax[1]:=1; ax[2]:=-1; ax[3]:=0; ax[4]:=0;
  ay[1]:=0; ay[2]:=0;  ay[3]:=1; ay[4]:=-1;
  for i:=1 to p do
    for j:=1 to p do gb[i,j]:=false;
  for k1:=1 to n do
    for k2:=1 to n do
      for k:=1 to 4 do
        if hf(k1+ax[k],k2+ay[k]) then begin
          gb[g[k1+ax[k],k2+ay[k]],g[k1,k2]]:=true;
          gb[g[k1,k2],g[k1+ax[k],k2+ay[k]]]:=true;
        end;
//**********************************************
  for i:=0 to p+1 do v[i].num:=0;
  for i:=1 to p do
    for j:=1 to p do begin
      if i=j then continue;
      if gb[i,j] then begin
        inc(v[i].num); q:=v[i].num;
        v[i].adj[q]:=j;
        v[i].long[q]:=h[j];
        inc(v[j].num); q:=v[j].num;
        v[j].adj[q]:=i;
        v[j].long[q]:=h[i];
      end;
    end;
  for i:=1 to p do hash[i]:=false;
  for i:=1 to n do hash[g[1,i]]:=true;
  for i:=1 to p do
    if hash[i] then begin
      inc(v[0].num); q:=v[0].num;
      v[0].adj[q]:=i;
      v[0].long[q]:=h[i];
    end;
  for i:=1 to p do hash[i]:=false;
  for i:=1 to n do hash[g[n,i]]:=true;
  for i:=1 to p do
    if hash[i] then begin
      inc(v[i].num); q:=v[i].num;
      v[i].adj[q]:=p+1;
      v[i].long[q]:=0;
    end;
  Dijsktra;
  if ans<h0 then writeln(fout,h0-ans)
  else writeln(fout,'NO');
  close(fin);
  close(fout);
end.