记录编号	39209	评测结果	AATTTTTTTA
题目名称	排队	最终得分	30
用户昵称	wo shi 刘畅	是否通过	未通过
代码语言	Pascal	运行时间	7.014 s
提交时间	2012-07-06 18:17:04	内存使用	16.39 MiB

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.