Skiing Down the Mountain

Bessie and her friends head for a skiing trip up a mountain. The mountain has \(N\) markers labeled \(1,2,\ldots,N\) in increasing order of altitude (marker \(1\) is at the base). For every marker \(i>1\) there is a ski slope from marker \(i\) to marker \(p_i\) (with \(1\le p_i < i\)). This slope has a difficulty \(d_i\) (\(0\le d_i\le10^9\)) and contributes a fun value of \(e_i\) (\(0\le e_i\le10^9\)).

Bessie’s \(M\) friends will each perform the following procedure: choose a starting marker \(i\) and ski downwards along the unique path: \(i\), \(p_i\), \(p_{p_i}\), …, until reaching marker \(1\). A friend collects a total fun equal to the sum of the fun values on all slopes they pass.

However, each friend has two parameters: a skill level \(s_j\) (\(0\le s_j\le10^9\)) and a courage factor \(c_j\) (\(0\le c_j\le10\)). They can only choose a starting marker \(i\) if, on the path from \(i\) to \(1\), there are at most \(c_j\) slopes whose difficulty exceeds \(s_j\) (i.e. for which \(d_i > s_j\)).

Your task is to compute, for each friend, the maximum total fun value they can achieve by choosing an appropriate starting marker.

Note: If a friend’s chosen path has \(k\) slopes and \(k \le c_j\), then the friend is allowed to take that path no matter what the slope difficulties are.

In other words, for a given friend with parameters \(s\) and \(c\), if you denote by fun(i) the total fun from marker \(i\) down to marker \(1\) and by difficult(i, s) the number of slopes on that path with \(d > s\), then the marker \(i\) is a valid choice if and only if either the number of slopes \(difficult(i, s)\) is \(\le c\) (if \(\text{depth}(i)\le c\)) or, when \(\text{depth}(i)>c\), the \((c+1)\text{-th}\) highest difficulty on the path is \(\le s\).

Your output for each friend should be the maximum achievable fun value among all valid starting markers.

inputFormat

The first line contains two integers \(N\) and \(M\) \((1 \le N, M \le 10^5)\).

For the next \(N-1\) lines (for markers \(2,3,\ldots,N\)), each line contains three integers \(p_i, d_i, e_i\) where \(1 \le p_i < i\), \(0 \le d_i \le 10^9\), and \(0 \le e_i \le 10^9\).

Then, the following \(M\) lines describe the friends. Each line contains two integers \(s_j\) and \(c_j\) \((0 \le s_j \le 10^9, 0 \le c_j \le 10)\), representing the friend's skill level and courage.

outputFormat

Output exactly \(M\) lines. The \(j\)-th line should contain a single integer: the maximum total fun value the \(j\)-th friend can achieve.

sample

3 3
1 5 10
2 3 5
5 0
3 0
3 1

15
0
15