const maxn=1001;
var
 h:array[0..maxn] of longint; w,a:array[0..maxn,0..maxn] of longint;
 i,j,n,k,min,ans,l,t:longint; v:array[0..maxn] of boolean;
 procedure insert(x,y:longint);
 begin
  inc(a[x,0]); a[x,a[x,0]]:=y;
 end;
 procedure dfs(k,now,dep:longint);
 var i,m:longint;
 begin
  if dep=n then
   begin
    if now<ans then ans:=now;
    exit;
   end;
  //zuiyouxing
  if now+min*(n-dep+1)>ans then exit;
  //kexingxing
  m:=maxlongint;
  for i:=1 to k do
   if (h[k]-h[i]>k) and (h[i]<m) and not v[i] then m:=h[i];
  for i:=1 to a[k,0] do
   if (not v[a[k,i]]) and (h[a[k,i]]-m<=k) then
    begin
     v[a[k,i]]:=true;
     dfs(a[k,i],now+w[k,a[k,i]],dep+1);
     v[a[k,i]]:=false;
    end;
  end;
begin
 assign(input,'queuea.in'); reset(input);
 assign(output,'queuea.out'); rewrite(output);
 readln(n,k);
 for i:=1 to n do read(h[i]);
 min:=maxlongint;
 for i:=1 to n do
  for j:=1 to n do
   begin
    read(w[i,j]);
    if w[i,j]<>0 then
     if min>w[i,j] then min:=w[i,j];
   end;
 for i:=1 to n do
  for j:=i+1 to n do
   if abs(h[i]-h[j])<=k then
    begin
     insert(i,j); insert(j,i);
    end;
 for i:=1 to n do
  for j:=1 to a[i,0] do
   for l:=1 to a[i,0]-j do
    if w[i,a[i,l]]<w[i,a[i,l+1]] then
     begin t:=a[i,l]; a[i,l]:=a[i,l+1]; a[i,l+1]:=t; end;
 ans:=maxlongint;
 v[1]:=true;
 dfs(1,0,1);
 writeln(ans);
 close(input); close(output);
end.