#include<cstring>
#include<iostream>
#include<cstdio>

using namespace std;
int n,m,ans,temp,times;
int sum[25],fa[25],k[25],p[25],a[25],s[25][25];

void dfs(int x){
	times++;
	if (times>8888888) return ;
	int i;
	if (x==n+1){
		sum[0]=0;
		for (i=1;i<=n;i++){
			sum[i]=sum[i-1]+s[fa[i]][i];
		}
		temp=sum[n];
		for (i=1;i<=m;i++){
			if (sum[k[i]]>=p[i]){
				temp+=a[i];
			}
		}
		ans=max(ans,temp);
		return ;
	}
	for (i=1;i<=n;i++){
		if (fa[i]) continue;
		fa[i]=x;
		dfs(x+1);
		fa[i]=0;
	}
}

int main(){
	freopen("deca.in","r",stdin);
	freopen("deca.out","w",stdout);
	int i,j;
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&k[i],&p[i],&a[i]);
	}
	for (i=1;i<=n;i++) 
	 for (j=1;j<=n;j++){
	 	scanf("%d",&s[i][j]);
	 }
	 times=0;
	ans=0;
	memset(fa,0,sizeof(fa));
	dfs(1);
	cout<<ans<<endl;
}