Kozak Vus and the Holiday#10164

Kozak Vus and the Holiday

2.5 seconds

256.642 megabytes

Hard

In the kingdom of Potokolandia, the residents are known for their meticulous nature, especially when it comes to planning celebrations. They schedule all events a century in advance to ensure everything runs smoothly. Cossack Vus wants to invite his friend, Cossack Vukh, to visit one of the kingdom's cities and attend as many celebrations as possible.

The kingdom consists of $n$ cities connected by $n - 1$ n-1 bidirectional roads, allowing travel between any two cities, possibly via other cities. Traveling along the $i$ -th road takes $l_{i}$ l_i days.

Each celebration in Potokolandia is defined by the city number $c_{i}$ c_i where it occurs and the day number $d_{i}$ d_i when it takes place. Cossack Vukh is efficient with his time; if he attends a celebration on day $i$ , he can leave that same day, arrive in another city the next day (if the road travel time $l_{i} = 1$ l_i=1), and attend another celebration if one is scheduled.

Cossack Vukh is fortunate to arrive in the kingdom on day $0$ and can initially choose to arrive in any city. Cossack Vus wants to determine the maximum number of celebrations his friend can attend and seeks your help to find this out.

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) — the number of cities in the kingdom.

Each of the next $n - 1$ n-1 lines contains three integers $a_{i}$ a_i, $b_{i}$ b_i, and $l_{i}$ l_i ( $1 \leq a_{i}, b_{i} \leq n$ 1 \le a_i, b_i \le n, $1 \leq l_{i} \leq 1 0^{9}$ 1 \le l_i \le 10^9) — the cities connected by the road and the number of days required to travel it. The graph is guaranteed to be connected.

The next line contains a single integer $m$ ( $1 \leq m \leq 2 \cdot 1 0^{5}$ 1 \le m \le 2 \cdot 10^5) — the number of celebrations in the kingdom.

Each of the next $m$ lines contains two integers $c_{i}$ c_i and $d_{i}$ d_i ( $1 \leq c_{i} \leq n$ 1 \le c_i \le n, $1 \leq d_{i} \leq 1 0^{9}$ 1 \le d_i \le 10^9) — the city number and the day number of the $i$ -th celebration.

Output

Output a single number — the maximum number of celebrations Cossack Vukh can attend.

Examples

Example 1

Example 2

Note

For example, Cossack Vukh can initially arrive in city $3$ and wait one day for a celebration. On the first day, he can travel for two days to city $1$ , where a celebration occurs on the third day. On the third day, he can travel to city $2$ , where another celebration is held on the fourth day. However, he cannot attend the last celebration because it takes $3$ days to reach city $4$ . Thus, he attends $3$ celebrations.