var
  n,k,i,j,ans,time:longint;
  h:array[1..1000] of longint;
  a:array[1..1000,1..1000] of longint;
  p:array[1..1000] of boolean;
  function max(x,y:longint):longint;
  begin if x>y then max:=x else max:=y; end;
  procedure dfs(num,sum,step,maxh:longint);
  var
    i:longint;
  begin
    time:=time+1;
    if step=n then
      begin
        if sum<ans then
          ans:=sum;
        exit;
      end;
    if time>20000000 then
      begin
        writeln(ans);
        close(input); close(output);
        halt;
      end;
    if sum>ans then exit;
    for i:=1 to n do
      if not p[i] then
        if maxh-h[i]<k then
          begin
            p[i]:=true;
            dfs(i,sum+a[num,i],step+1,max(maxh,h[i]));
            p[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]);
  for i:=1 to n do
    for j:=1 to n do
      read(a[i,j]);
  p[1]:=true;
  ans:=maxlongint;
  dfs(1,0,1,h[1]);
  writeln(ans);
  close(input); close(output);
end.