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 100000)$ and $Q$ $(1\le Q\le 100000)$, 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$.