P8548 Xiao Wa Buys Flowers

Xiao Wa likes buying flowers, but they are too lazy. So this task is completely handed over to you.

There are only $n$ flowers in the shop. Each flower has three attributes: price $cost_i$, beauty $be_i$, and freshness $fr_i$. Xiao Wa has different requirements each time. More precisely, for the $j$-th purchase, the money you have can buy flowers with **total cost at most $c_j$**. At the same time, Xiao Wa also requires that the **total freshness is at least $f_j$**. Xiao Wa wants to know: after meeting these conditions, what is the maximum possible **total beauty** of the flowers you buy? If no matter what you do, you cannot make the total freshness at least $f_j$, output $0$. Xiao Wa will ask you to buy flowers a total of $q$ times. Can you answer their questions correctly? The queries are independent of each other.

The first line contains two positive integers $n, q$. Lines $2 \sim n + 1$ each contain three positive integers $cost_i, fr_i, be_i$, representing the three attributes of a flower. Lines $n + 2 \sim n + q + 1$ each contain two positive integers $c_j, f_j$, representing the requirements for each purchase.

Output $q$ lines. Each line contains one integer, the maximum total beauty. If there is no solution, output $0$.

For $20\%$ of the testdata, $3\leq n, q\leq 16$. For $40\%$ of the testdata, $3\leq n, q\leq 30$, $0\leq c_j, f_j\leq 50$. For $60\%$ of the testdata, $3\leq n\leq 100$, $1\leq q\leq 5\times 10^4$, $0\leq cost_i, fr_i, c_j, f_j\leq 100$. For the other $20\%$ of the testdata, for each purchase, $f_j = 0$. For $100\%$ of the testdata, $3\leq n\leq 500$, $\boldsymbol{1\leq q\leq 10^6}$, $0\leq cost_i, fr_i, c_j, f_j\leq 500$, $1\leq be_i \leq 10^6$. Translated by ChatGPT 5