var
  a:array[0..25,0..25] of longint;
  v:array[0..25] of boolean;
  f:array[0..25] of longint;
  ans,temp,n,k:longint;
  aa,bb,cc,dd:array[0..25] of longint;

procedure init;
 var i,j,t:longint;
begin
   readln(n,k);
   for i:=1 to k do
   readln(aa[i],bb[i],cc[i]);
   for i:=1 to n do
    begin
       for j:=1 to n do
       read(a[i,j]);
       readln;
    end;
end;

procedure work;
var i:longint;
begin
  f[0]:=0;
  for i:=1 to n do
    f[i]:=f[i-1]+a[dd[i],i];
  temp:=0;
  for i:=1 to k do
   if f[aa[i]]>=bb[i] then inc(temp,cc[i]);
 if ans<f[n]+temp then ans:=f[n]+temp;
end;

procedure dfs(xx,ww:longint);
var i,j:longint;
begin
   if ww=n-1 then
    begin
      for i:=1 to n do
      if v[i] then
       begin  dd[i]:=xx;break;end;
     work;
   exit;
    end;
  for i:=1 to n do
   if v[i] then
   begin
    v[i]:=false;
    dd[i]:=xx;
    dfs(xx+1,ww+1);
    v[i]:=true;
   end;
end;

procedure main;
begin
   ans:=0;
   fillchar(v,sizeof(v),1);
   fillchar(dd,sizeof(dd),0);
   dfs(1,0);
   writeln(ans);
end;

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