记录编号	7603	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 埃雷萨拉斯的宝藏	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	Pascal	运行时间	0.340 s
提交时间	2008-11-10 19:42:53	内存使用	24.06 MiB

program eldrethalas;
 const
   d:array[1..4,1..2] of integer=((0,1),(0,-1),(1,0),(-1,0));
   maxn=50;
 var
    n,p,h:longint;
    a:array[1..maxn,1..maxn] of longint;
    va:array[0..maxn*maxn+4] of longint;
    cost:array[0..maxn*maxn+1,0..maxn*maxn+1] of longint;

procedure init;
 var
     i,j,k,x,y:longint;

 begin
  readln(n,p,h);
  for i:=1 to p do
  read(va[i]);
  for i:=1 to n do
    for j:=1 to n do
    read(a[i,j]);
  fillchar(cost,sizeof(cost),$FF);
  inc(p);
  for i:=0 to p do cost[i,i]:=0;
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to 4 do
        begin
         x:=i+d[k,1]; y:=j+d[k,2];
         if (x>=1) and (x<=n) and (y>=1) and (y<=n)
         then if a[x,y]<>a[i,j]
              then
                   cost[a[i,j],a[x,y]]:=va[a[x,y]];
        end;
  for i:=1 to n do cost[0,a[1,i]]:=va[a[1,i]];
  for i:=1 to n do cost[a[n,i],p]:=0;
 end;


procedure main(v0:longint);
 var
    i,j,k,min:longint;
    lowcost:array[0..2500+4] of longint;
    mark:array[0..2500+4] of boolean;

 begin
  for i:=0 to p do lowcost[i]:=maxlongint;
  lowcost[v0]:=0;
  fillchar(mark,sizeof(mark),0);
  for i:=0 to p-1 do
    begin
      min:=maxlongint;
      for j:=0 to p do
      if not mark[j] and (lowcost[j]<min)
      then begin
           min:=lowcost[j]; k:=j
           end;
      mark[k]:=true;
      for j:=0 to p do
      if cost[k,j]<>-1
      then if lowcost[k]+cost[k,j]<lowcost[j]
           then lowcost[j]:=lowcost[k]+cost[k,j];
    end;
 if h>lowcost[p] then writeln(h-lowcost[p])
                 else writeln('NO');
 end;


begin
  assign(input,'eldrethalas.in');
  assign(output,'eldrethalas.out');
  reset(input); rewrite(output);
  init;
  main(0);
  close(input); close(output);
end.