405645: GYM102020 L Looter of Fridges

Once upon a time, on a certain university's center, there was a thief that kept stealing grated cheese from the kitchen's fridge. As time passed by, he also began to steal lunch boxes.

It is known that on the beginning of a certain day, all students put their lunch boxes on the fridge, and then, each student will retrieve its lunch box on a specific moment in time to eat it.

Besides that, each lunch box has a warning level, that is a value which depends on many factors (e.g.: in case the student likes to complain on the center's e-mail, the warning level is quite high). The lunch boxes also have a taste level, which ranks how good they are.

Therefore, the thief wants to know, in case he decides to steal at some moment in time, the maximum level of taste he can get, without letting the warning level exceed a given limit, because, if this limit happen to be exceeded, the center will adopt some measures in order to stop the thievery, something that the thief certainly does not want.

The total taste and warning levels are, respectively, the sum of the tastiness and the sum of the warning levels of all the lunch boxes the thief plans on stealing at that moment.

If it happens that a student goes to retrieve his lunch box on the same time the thief goes to steal the fridge, the thief will then wait for the student to retrieve his lunch box and then proceed to rob the fridge.

The first line of input contains two integers $$$N$$$ and $$$Q$$$ ($$$0 \le N \le 10^4$$$, $$$1 \le Q \le 2 \cdot 10^5$$$), the number of lunch boxes and the number of moments in time that the thief can go rob the fridge, respectively.

Then, $$$N$$$ lines follow, where the $$$i$$$-th of them contains three integers $$$V_i$$$, $$$W_i$$$ and $$$E_i$$$ ($$$0 \le V_i \le 10^5$$$, $$$0 \le W_i \le 10^6$$$ e $$$1 \le E_i \le 10^9$$$), the tastefulness level, the warning level and the time at which the $$$i$$$-th lunch box is retrieved from the fridge, respectively.

Finally, there will be $$$Q$$$ more lines, where the $$$i$$$-th of them contains two integers $$$T_i$$$ and $$$K_i$$$ ($$$0 \le T_i \le 10^9$$$, $$$0 \le K_i \le 10^4$$$), representing the moment in time where the thief will go rob the fridge and the warning level limit on that moment.

Your program must output $$$Q$$$ lines, the $$$i$$$-th of them containing a single integer, representing the highest tastefulness level the thief can obtain at the moment $$$T_i$$$, without letting the warning level exceed $$$K_i$$$.

3 2
3 1 1
2 2 3
1 3 4
0 4
2 4

5
2