#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
int n,b;
int f[1<<21];
int s[22][22];
struct node{
    int k,p,a;
}e[22];

bool cmp(node a,node b){
    return a.p < b.p;
}

int lowbit(int x){
    return x & -x;
}

int count(int x){
    int cnt=0;
    for(int i=x;i;i-=lowbit(i)){
        cnt++;
    }
    return cnt;
}

int main(){
    scanf("%d%d",&n,&b);
    for(int i=1;i<=b;i++){
        scanf("%d%d%d",&e[i].k,&e[i].p,&e[i].a);
    }
    sort(e+1,e+1+b,cmp);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&s[i][j]);
        }
    }
    int maxn = 1<<n;
    for(int i=0;i<maxn;i++){
        int game = count(i);
        for(int j=1;j<=n;j++){
            if(i&(1<<(j-1))){
                f[i] = max(f[i],f[i^(1<<(j-1))]+s[j][game]);
            }
        }
        for(int j=1;j<=b;j++){
            if(e[j].k==game&&f[i]>=e[j].p)f[i]+=e[j].a;
        }
    }
    printf("%d\n",f[maxn-1]);
    return 0;
}