ofcourse doing dp knapsack on each query will give Time limit exceeded with this contrains.

you should think a better solution

You can initialize segment tree with knapsack DP for each segment — O(N * log(N) * B). Then you can answer single query in O(log(N) * B^2). Each vertex of segment tree contains a vector p of length B + 1. p[i] is a maximal profit you can get for i dollars using only cards from corresponding subsegment. To combine two segments a and b run for i in 0..B for j int 0..B-i c[i + j] = max(c[i + j], a[i] + b[j]); Total O(N * log(N) * B + D * log(N) * B^2)