题目描述

众所周知，波托科兰迪亚王国的居民是非常严谨细致的人。即使是在节日这件事上，他们也总是希望确保一切都能顺利进行。因此，所有节日的日程都提前一百年就安排好了。哥萨克胡子决定邀请他的朋友——哥萨克耳朵，前来王国中的某个城市，并尽可能多地参加节日。

王国有 $n$ 个城市，通过 $n-1$ 条双向道路连接，使得从任何一个城市都可以到达另一个城市（可能需要经过其他城市）。通过第 $i$ 条道路需要 $l_i$ 天时间。

波托科兰迪亚的每个节日由举办城市的编号 $c_i$ 和举办日期的编号 $d_i$ 来描述。哥萨克耳朵在庆祝上不花费太多时间。因此，如果他在第 $i$ 天庆祝，那么他可以在同一天出发，并在第二天到达另一个城市（如果存在一条 $l_i = 1$ 的道路），并参加庆祝（如果该城市有节日）。

哥萨克胡子的这位朋友非常幸运，他抵达王国的日期在日历上的编号是 $0$，并且他一开始可以选择到达王国的任何一个城市。哥萨克胡子想知道，他的朋友最多能参加多少个节日。为此，他向您求助。请帮助他解决这个问题！

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$) —— 王国中的城市数量。

接下来的 $n-1$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $l_i$ ($1 \le a_i, b_i \le n$, $1 \le l_i \le 10^9$) —— 表示道路连接的两个城市的编号，以及通过该道路所需的天数。保证图是连通的。

下一行包含一个整数 $m$ ($1 \le m \le 2 \cdot 10^5$) —— 王国中的节日数量。

接下来的 $m$ 行，每行包含两个整数 $c_i$ 和 $d_i$ ($1 \le c_i \le n$, $1 \le d_i \le 10^9$) —— 表示第 $i$ 个节日的举办城市编号和举办日期。

输出格式

输出一个数字 —— 哥萨克耳朵最多能够参加的节日数量。

4
1 2 1
2 3 1
2 4 3
4
1 3
2 4
3 1
4 5

3

11
2 1 2
3 2 5
4 1 5
5 2 4
6 5 1
7 1 2
8 3 4
9 6 2
10 7 2
11 2 2
9
1 67
1 34
11 16
5 97
4 70
2 20
2 61
2 26
2 70

8

提示

一开始，哥萨克耳朵可以到达城市 $3$ 并等待一天直到庆祝。之后，在第一天，他可以用两天时间移动到城市 $1$，那里在第三天将举行节日。同样，在第三天，他可以出发前往城市 $2$，那里在第四天也有节日。但他已经赶不上最后一个节日了，因为到达城市 $4$ 需要 $3$ 天时间。因此，他参加了 $3$ 个节日。

$$\begin{array}{|c|c|c|c|c|} \hline \rule{0pt}{1.5em} \textbf{子任务编号} & \textbf{n} & \textbf{m} & \textbf{l\_i, d\_i} & \textbf{分值} \\ \hline \rule{0pt}{1.5em} 1 & 1 \le n \le 100 & 1 \le m \le 9 & 1 \le l_i, d_i \le 100 & 14 \\ \hline \rule{0pt}{1.5em} 2 & 1 \le n \le 2000 & 1 \le m \le 2000 & 1 \le l_i, d_i \le 5000 & 17 \\ \hline \rule{0pt}{1.5em} 3 & 1 \le n \le 5000 & 1 \le m \le 5000 & 1 \le l_i, d_i \le 10^9 & 28 \\ \hline \rule{0pt}{1.5em} 4 & 1 \le n \le 10^5 & 1 \le m \le 10^5 & 1 \le l_i, d_i \le 10^9 & 22 \\ \hline \rule{0pt}{1.5em} 5 & 1 \le n \le 2 \cdot 10^5 & 1 \le m \le 2 \cdot 10^5 & 1 \le l_i, d_i \le 10^9 & 19 \\ \hline \end{array}$$