#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
 const int u=30;
 int s[u][u],a[u],p[u];
 int ans,n,b;
 bool v[u];
 
 int dfs(int x,int mark){
 	int now=0;
 	if (x>n) return now;
 	for (int j=1; j<=n; j++)
 	 if (!v[j]){
 	 	v[j]=1;
 	 	int rr=s[x][j];
 	 	if (mark+rr>=p[x]) rr+=a[x];
 	 	rr+=dfs(x+1,mark+rr);
 	 	now=max(now,rr);
 	 	v[j]=0;
 	 }
 	 return now;
 }
 
 void work(){
 	memset(v,0,sizeof(v));
 	ans=dfs(1,0);
 }
 
int main(){
	freopen("deca.in","r",stdin);
	freopen("deca.out","w",stdout);
	scanf("%d%d",&n,&b);
	int i;
	for (i=1; i<=b; i++){
		int temp,x,y;
	    scanf("%d%d%d",&temp,&x,&y);
	    p[temp]=x;
	    a[temp]=y;
    }
  /* p[0]=0; a[0]=0;
    for (i=1; i<=n; i++){
    	if (a[i]==0&&p[i]==0){
    		a[i]=a[i-1];
    		p[i]=p[i-1];
    	}
    }
*/    
	for (i=1; i<=n; i++)
	 for (int j=1; j<=n; j++)
	   scanf("%d",&s[j][i]);
	work();
	printf("%d",ans);
	return 0;
}