Bob lives in a city with ~N~ skyscrapers arranged in a row running north to south. He likes to hang glide over the city. Bob can glide south to a shorter building if all of the passed buildings' heights are smaller than his current building's height.

Each of the ~N~ buildings has height ~h_i~, view value ~v_i~, and danger value ~d_i~ for ~1 \le i \le N~. Bob has ~Q~ questions for you: Given that he starts at the ~B^{th}~ northmost building ~(1 \le B \le N)~, what is the maximum possible sum of the view values of buildings which he lands on such that none of those buildings has danger value more than ~M~ ~(1 \le M \le 10^6)~?

Input Specification

The first line contains two space-separated numbers ~N~ ~(1 \le N \le 100\,000)~ and ~Q~ ~(1 \le Q \le 100\,000)~, the number of buildings and queries respectively.
The next ~N~ lines each contain ~h_i~ ~(1 \le h_i \le 10^6)~, ~v_i~ ~(1 \le v_i \le 10^6)~, and ~d_i~ ~(1 \le d_i \le 10^6)~, the height, view value, and danger value for the ~i^{th}~ northmost building.
The next ~Q~ lines each contain the query. Each line contains two space-separated numbers ~B~ ~(1 \le B \le N)~ and ~M~ ~(1 \le M \le 10^6)~. It is guaranteed that the danger value of the ~B^{th}~ northmost building is not more than ~M~.

Output Specification

For each query, output the answer on a new line.

Sample Input 1

3 2
3 1 2
3 4 4
1 2 10
2 20
2 4

Sample Output 1

6
4

Explanation

For the first query, the path which maximizes the sum of view values is hang gliding to the third building, so the answer is ~4+2~. For the second query, the path which maximizes the sum of view values is simply staying put at the second building, so the answer is ~4~.