Flower Shop Challenge

You are given n flowers, each with three attributes: cost \(cost_i\), beauty \(be_i\), and freshness \(fr_i\). You need to answer q independent queries. For the j-th query, you have a budget that can buy flowers with a total cost at most \(c_j\), and the total freshness of the chosen flowers should be at least \(f_j\). Your task is to maximize the sum of the beauty of the selected flowers. If no valid subset of flowers meets the conditions, output -1.

Input Format

The first line contains two integers \(n\) and \(q\), representing the number of flowers and the number of queries. Each of the next \(n\) lines contains three integers: \(cost_i\), \(be_i\), \(fr_i\). Each of the following \(q\) lines contains two integers \(c_j\) and \(f_j\).

Output Format

For each query, output a single line with the maximum total beauty sum satisfying the conditions, or -1 if no valid subset exists.

Note: The conditions for each query are independent of each other.

inputFormat

The first line contains two integers \(n\) and \(q\).
The next \(n\) lines each contain three integers \(cost_i\), \(be_i\), \(fr_i\).
Then \(q\) lines follow, each containing two integers \(c_j\) and \(f_j\).

outputFormat

For each query, output the maximum beauty sum of a valid set of flowers or -1 if it is impossible to meet the conditions.

sample

3 3
3 6 4
2 5 3
4 7 2
5 5
9 6
3 4

11
18
6