Description

Hint

#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&#44; 0&#44; sizeof(f));
for(int i=0; i&lt;(1&lt;&lt;n); i++){
	int t=0;
	for(int j=1; j&lt;=n; j++) if(i&amp;(1&lt;&lt;(j-1))) t++;
	for(int j=1; j&lt;=n; j++) if(i&amp;(1&lt;&lt;(j-1))){
		f[i]=max(f[i]&#44; f[i^(1&lt;&lt;(j-1))]+s[j][t]);
	}
	for(auto j: G[t]) if(f[i]&gt;=j.p){
		f[i]+=j.a;
	}
} 
printf("%lld\n"&#44; f[(1&lt;&lt;n)-1]);
return 0;

}