by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=22;
typedef long long LL;
struct node{LL p, a;}; vector<node> G[N]; 
LL s[N][N], f[(1<<N)];
bool cmp(node n1, node n2) {return n1.p<n2.p;}
int main(){
	int n, m; scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++){
		int k; LL p, a;
		scanf("%d%lld%lld", &k, &p, &a);
		G[k].push_back({p, a});
	}
	for(int i=1; i<=n; i++) sort(G[i].begin(), G[i].end(), cmp);
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++)
		scanf("%lld", &s[i][j]);
		
	memset(f, 0, sizeof(f));
	for(int i=0; i<(1<<n); i++){
		int t=0;
		for(int j=1; j<=n; j++) if(i&(1<<(j-1))) t++;
		for(int j=1; j<=n; j++) if(i&(1<<(j-1))){
			f[i]=max(f[i], f[i^(1<<(j-1))]+s[j][t]);
		}
		for(auto j: G[t]) if(f[i]>=j.p){
			f[i]+=j.a;
		}
	} 
	printf("%lld\n", f[(1<<n)-1]);
	return 0;
}

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=22;
typedef long long LL;
struct node{LL p, a;}; vector<node> G[N]; 
LL s[N][N], f[(1<<N)];
bool cmp(node n1, node n2) {return n1.p<n2.p;}
int main(){
	int n, m; scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++){
		int k; LL p, a;
		scanf("%d%lld%lld", &k, &p, &a);
		G[k].push_back({p, a});
	}
	for(int i=1; i<=n; i++) sort(G[i].begin(), G[i].end(), cmp);
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++)
		scanf("%lld", &s[i][j]);
		
	memset(f, 0, sizeof(f));
	for(int i=0; i<(1<<n); i++){
		int t=0;
		for(int j=1; j<=n; j++) if(i&(1<<(j-1))) t++;
		for(int j=1; j<=n; j++) if(i&(1<<(j-1))){
			f[i]=max(f[i], f[i^(1<<(j-1))]+s[j][t]);
		}
		for(auto j: G[t]) if(f[i]>=j.p){
			f[i]+=j.a;
		}
	} 
	printf("%lld\n", f[(1<<n)-1]);
	return 0;
}