var
 map:array[1..1000,1..1000]of longint;
 h,d,f,num,temp:array[1..1000]of longint;
 v:array[1..1000]of boolean;
 ans,i,j,k,n,l,min,mm:longint;

 procedure dfs(dn,x,m:longint);
  var i:longint;
  begin
    if m>=ans then exit;
    if dn=n then begin ans:=m;exit;end;
    if m+(n-dn)*mm>=ans then exit;

    v[x]:=true;
    for i:=num[x]to n do dec(d[i]);
    for i:=2 to n do
     if (v[i]=false)and(d[i]=0)then dfs(dn+1,i,m+map[x,i]);
    v[x]:=false;
  end;

begin
assign(input,'queuea.in');reset(input);
assign(output,'queuea.out');rewrite(output);
 readln(n,k);
 mm:=maxlongint;
 for i:=1 to n do read(h[i]);
 for i:=1 to n do
  for j:=1 to n do
    begin
     read(map[i,j]);
     if (map[i,j]<>0)and(map[i,j]<mm)then mm:=map[i,j];
    end;

 ans:=0;
 for i:=1 to n-1 do
  begin
   j:=i+1;
   while (h[j]-h[i]<k)and(j<=n) do inc(j);
   num[i]:=j;
   for l:=j to n do inc(d[l]);
  end;
 temp:=d;
 num[n]:=n+1;

 fillchar(v,sizeof(v),0);
 f[1]:=1;v[1]:=true;
 for i:=num[1] to n do dec(d[i]);

 for i:=2 to n do
  begin
   min:=maxlongint;l:=0;
   for j:=2 to n do
    if (v[j]=false)and(d[j]=0)and(map[f[i-1],j]<min) then
     begin min:=map[f[i-1],j];l:=j;end;
   f[i]:=l;v[l]:=true;
   for j:=num[f[i]]to n do dec(d[j]);
   inc(ans,min);
  end;

 fillchar(v,sizeof(v),0);
 d:=temp;
 dfs(1,1,0);
 writeln(ans);
close(input);close(output);
end.