#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,ans;
int w[21][21];
int order[21],s[21],a[21],b[21],c[21];
bool v[21];
void work(){
	int tem=0;
	for(int i=1;i<=n;++i){
	    tem+=w[order[i]][i];
		s[i]=s[i-1]+w[order[i]][i];	
	}
	for(int i=1;i<=m;++i)
	if (s[a[i]]>=b[i]) tem+=c[i];
	if (tem>ans) ans=tem;
}
void so(int x){
	if(x>n) {
		work();
		return;
	}
    for(int i=1;i<=n;++i)
    if (!v[i]){
    	v[i]=true;
    	order[x]=i;
    	so(x+1);
    	v[i]=false;
    }
}
int main(){
	freopen("deca.in","r",stdin);
	freopen("deca.out","w",stdout);
	int i,j;
	cin>>n>>m;
	for(i=1;i<=m;++i){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	}
	for(i=1;i<=n;++i)
	  for(j=1;j<=n;++j){
	  	 scanf("%d",&w[i][j]);
	  }
	memset(v,0,sizeof(v));
	ans=0;
	so(1);
	cout<<ans<<endl;
	
}