var
  g,f:array[0..1000,0..1000]of longint;
  a,ru:array[0..1000000]of longint;
  v:array[0..1000000]of boolean;
  n,k,i,j,ans:longint;

procedure go(k,s,m:longint);
var
  i,j,u:longint;
begin
  if s>ans then exit;
  if m=n then
  begin
    if s<ans then ans:=s;
    exit;
  end;
  for i:=1 to n do
  if (not v[i])and(ru[i]=0) then
  begin
    for j:=1 to g[i,0] do
    begin
      u:=g[i,j];
      dec(ru[u]);
    end;
    v[i]:=true;
    go(i,s+f[k,i],m+1);
    v[i]:=false;
    for j:=1 to g[i,0] do
    begin
      u:=g[i,j];
      inc(ru[u]);
    end;
  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(a[i]);

  for i:=1 to n do
   for j:=1 to n do
   read(f[i,j]);

  for i:=1 to n do
   for j:=1 to n do
   if a[j]-a[i]>=k then
   begin
     inc(ru[j]);
     inc(g[i,0]);
     g[i,g[i,0]]:=j;
   end;

  ans:=maxlongint;
  for i:=1 to g[1,0] do dec(ru[g[1,i]]);
  v[1]:=true;
  go(1,0,1);
  writeln(ans);
  close(input);
  close(output);
end.