记录编号	96693	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14] 奶牛的十项全能	最终得分	100
用户昵称	zgyzhaoguangyang	是否通过	通过
代码语言	Pascal	运行时间	2.349 s
提交时间	2014-04-14 15:50:12	内存使用	4.18 MiB

var
   f:Array[0..1050000] of longint;
   a:array[0..25,0..25] of longint;
   aa,bb,cc:array[0..25] of longint;
   a1,b1:array[0..25,0..25] of longint;
   c:array[0..25] of longint;
   n,k:longint;
procedure init;
var i,j:longint;
begin
    readln(n,k);
   fillchar(a1,sizeof(a1),0);
   fillchar(b1,sizeof(b1),0);
	 for i:=1 to k do
         begin
	   readln(aa[i],bb[i],cc[i]);
           inc(c[aa[i]]);
           a1[aa[i],c[aa[i]]]:=bb[i];
           b1[aa[i],c[aa[i]]]:=cc[i];
         end;
         for i:=1 to n do
         begin
           for j:=1 to n do
              read(a[i,j]);
              readln;
            end;
end;

function max(xx,yy:longint):longint;
 begin
    if xx<=yy then exit(yy);
	  exit(xx)
 end;

 function getmany(xx:longint):longint;
 var temp:longint;
 begin
      temp:=0;
	   while xx>0 do
	     begin
		    inc(temp);
		     dec(xx,xx and (-xx));
             end;
		exit(temp);
 end;


function getok(x,kk:longint):boolean;
begin
   x:=x>>(kk-1);
  if (x and 1=0) then exit(false);
   exit(true);
end;

procedure main;
var i,j,x,temp,ans,l,temp2:longint;
begin
    fillchar(f,sizeof(f),0);
     for i:=1 to (1<<n-1) do
       begin
          ans:=0;
          x:=getmany(i);
           for j:=1 to n do
            if getok(i,j) then
             begin
                temp:=0;temp2:=0;
                temp:=f[i xor (1<<(j-1))]+a[j,x];
                //if temp>=a1[x] then inc(temp,b1[x]);
                for l:=1 to c[x] do
                 if temp>=a1[x,l] then inc(temp2,b1[x,l]);
                ans:=max(ans,temp2+temp);
             end;
          f[i]:=ans;
       end;
    writeln(f[1<<n-1]);
end;

begin
   assign(input,'deca.in');reset(input);
   assign(output,'deca.out');rewrite(output);
    init;main;
   close(input);close(output);
end.