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

var
   i,j:longint;
   y,x,n,q:longint;
   ki:array[1..20,1..20]of longint;
   k,a,b:array[1..1000]of longint;
   dp:array[0..1048576]of longint;
procedure swap(var x,y:longint);
var t:longint;
begin
     t:=x;x:=y;y:=t;
end;

procedure qsort(l,r:longint);
var i,j,x:longint;
begin
     i:=l;j:=r;x:=k[(l+r)shr 1];
     repeat
           while k[i]<x do inc(i);
           while k[j]>x do dec(j);
           if i<=j then
           begin
                swap(k[i],k[j]);
                swap(b[i],b[j]);
                swap(a[i],a[j]);
                inc(i);dec(j);
           end;
     until i>j;
     if i<r then qsort(i,r);
     if j>l then qsort(l,j);
end;


begin
     assign(input,'deca.in');
     reset(input);
     assign(output,'deca.out');
     rewrite(output);

     readln(n,q);
     for i:=1 to q do
       readln(k[i],b[i],a[i]);
     qsort(1,q);
     for i:=1 to n do
       for j:=1 to n do
       read(ki[i,j]);
     dp[0]:=0;
     for i:=1 to (1 shl n-1) do
       begin
            y:=0;
            for j:=0 to n-1 do
            if (i shr j) and 1 =1 then inc(y);
            for j:=0 to n-1 do
            if (i shr j) and 1 =1 then
            begin
                 x:=dp[i xor (1 shl j)]+ki[j+1,y];
                 if dp[i]<x then dp[i]:=x;
            end;
            for j:=1 to q do
              if (k[j]=y)and(dp[i]>=b[j]) then inc(dp[i],a[j]);
       end;
     writeln(dp[1 shl n -1]);

     close(input);close(output);
end.