#include
using namespace std;
struct doll { int w, v, e; inline void read() { scanf("%d%d%d", &w, &v, &e); } };
const int maxn = 1009; const int tv = 1000;
int n, q, bsz, fa[maxn][maxn], fr[maxn][maxn], f[maxn][maxn]; doll d[maxn];
void sglDP(int* f, doll d) { int e(d. e); for (int i = 1; i <= e; i «= 1) { e -= i; for (int j = tv; j >= i * d. w; – j) f[j] = max(f[j], f[j - i * d. w] + i * d. v); } if (e) for (int j = tv; j >= e * d. w; – j) f[j] = max(f[j], f[j - e * d. w] + e * d. v); }
void preBlock(int le, int re) { static int tmp[maxn]; memset(tmp, 0, sizeof(tmp)); for (int i = 0; i <= tv; ++ i) for (int j = 0; i + j <= tv; ++ j) tmp[i + j] = max(tmp[i + j], fa[le - 1][i] + fr[re + 1][j]); for (int i = le; i <= re; ++ i) { memcpy(f[i], tmp, sizeof(tmp)); for (int j = le; j <= re; ++ j) if (i != j) sglDP(f[i], d[j]); } }
int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
d[i]. read();
memset(fa[0], 0, sizeof(fa[0]));
for (int i = 1; i <= n; ++ i) {
memcpy(fa[i], fa[i - 1], sizeof(fa[i]));
sglDP(fa[i], d[i]);
}
memset(fr[n + 1], 0, sizeof(fr[n + 1]));
for (int i = n; i; -- i) {
memcpy(fr[i], fr[i + 1], sizeof(fr[i]));
sglDP(fr[i], d[i]);
}
bsz = (int)sqrt(n) + 1;
for (int i = 1; i <= n; i += bsz)
preBlock(i, min(n, i + bsz - 1));
scanf("%d", &q);
while (q --) {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", f[a + 1][b]);
}
}