Background

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

Problem Description

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.

Input Format

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 Format

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

5 1
2 4 5
4 3 3
1 3 2
3 4 3
3 2 5
10 10

15

Hint

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