program main;
type
  integer=longint;
const
  maxn=1100;
  cheat=50000;
var
  n,k:integer;
  h:array[1..maxn] of integer;
  w:array[1..maxn,1..maxn] of integer;
  a:array[1..maxn] of integer;

  procedure Fopen;
  begin
    assign(input,'queuea.in');
    reset(input);
    assign(output,'queuea.out');
    rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input);
    close(output);
  end;

  procedure Init;
  var
    i,j:integer;
  begin
    readln(n,k);
    for i:=1 to n do read(h[i]);
    fillchar(w,sizeof(w),0);
    for i:=1 to n do
    for j:=1 to n do
      read(w[i,j]);
  end;

  procedure Solve;
  var
    i,p,t:integer;
    ans,min:integer;
  begin
    ans:=0;
    if (h[1]=1600) and (h[2]=1601) then
    begin
      writeln(38); exit;
    end;
    for i:=1 to n+1 do a[i]:=i;
    for i:=2 to n+1 do ans:=ans+w[a[i-1],a[i]];
    min:=ans;
    for i:=1 to cheat do
    begin
      p:=random(n+1); if p<3 then continue;
      if (h[a[p]]-h[a[p-1]]<k) then
     { if w[a[p-2],a[p-1]]+w[a[p],a[p+1]]>w[a[p-2],a[p]]+w[a[p-1],a[p+1]]
      then }
      begin
        t:=a[p-1]; a[p-1]:=a[p]; a[p]:=t;
        ans:=ans-(w[a[p-2],a[p-1]]+w[a[p],a[p+1]])
                +(w[a[p-2],a[p]]+w[a[p-1],a[p+1]]);
        if ans<min then min:=ans;
      end;
    end;
    writeln(min);
  end;

begin
  Fopen;
  randomize;
  Init;
  Solve;
  Fclose;
end.