$\text{record}$

$\text{Code:}$

#include<bits/stdc++.h>
using namespace std;
const int N=5e2+7;
const int M=5e2+7;
const int K=500;
int n,q,a[N],b[N],c[N];
int f[M][M],ans[M][M],pre[M][M];
int main(){
	memset(ans,-0x3f,sizeof ans);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for(int i=1;i<=n;i++){
		for(int j=K;j>=a[i];j--){
			for(int k=K+1;k>=K-b[i]+1;k--)
				f[j][K+1]=max(f[j][K+1],f[j-a[i]][k]+c[i]);
			for(int k=K;k>=b[i];k--)
				f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+c[i]);
		}	
	}
	for(int j=0;j<=K;j++){
		for(int k=K+1;k>=0;k--){
			ans[j][k]=f[j][k];
			if(k<=K) ans[j][k]=max(f[j][k],ans[j][k+1]);
			if(j-1>=0) ans[j][k]=max(ans[j][k],ans[j-1][k]);
		}
	}
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",ans[x][y]);
	}
	return 0;
}

$\text{1.in:}$

16 16
13 190 150519
487 278 963895
311 445 999567
277 277 656425
82 232 970123
351 64 393056
492 468 329210
370 123 446733
190 452 542659
86 226 511286
14 43 855461
98 283 14229
355 145 418112
341 478 179540
246 263 518758
280 468 664876
322 288
87 400
352 117
282 162
344 411
464 143
221 141
172 268
183 5
450 328
288 67
361 59
152 242
250 324
6 73
458 145

$\text{1.out:}$

2518762
0
2518762
2487389
2518762
3030048
2487389
1976103
2336870
3030048
2487389
2518762
1976103
2487389
0
3030048

$\text{myprogramout:}$

2518762
1005980
...