Byteland 王国的道路网络由 $n$ 座城市组成，编号为 $1$ 到 $n$，由 $n-1$ 条双向道路连接。每条道路的长度均为 $1$。该道路网络是连通的，且其图结构是一棵树。

王国中共有 $m$ 座军事塔。第 $i$ 座塔位于城市 $a_i$，其保护范围半径为 $r_i$。如果城市 $v$ 到 $a_i$ 的旅行距离不超过 $r_i$，则称城市 $v$ 被第 $i$ 座塔保护。

Byteland 的国王准备选择其中一座城市作为新的首都。首都必须被所有的塔保护。国王可以投资扩展现有塔的保护范围。将任意一座塔的保护半径增加非负整数 $x$，需要花费 $\lceil \frac{x}{k} \rceil$ 枚金币。请找出国王为了能够选择一个被所有塔保护的首都，所需要花费的最少金币总数。

输入格式

第一行包含三个整数 $n, m, k$ ($1 \le n, m \le 10^5, 1 \le k \le 10$)，分别表示城市数量、塔的数量以及支付函数的除数。

接下来的 $n-1$ 行描述道路。第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$)，表示第 $i$ 条道路连接的城市编号。保证给定的图是一棵树。

接下来的 $m$ 行描述塔。第 $i$ 行包含两个整数 $a_i, r_i$ ($1 \le a_i \le n, 0 \le r_i \le 10^9$)，表示第 $i$ 座塔所在的城市编号及其保护半径。

输出格式

输出一个整数，表示为了能够选择一个新首都，在升级塔上所需花费的最少金币总数。

样例

样例输入 1

3 2 1
1 2
2 3
1 1
3 0

样例输出 1

1

样例输入 2

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

样例输出 2

4

样例输入 3

6 2 2
1 2
2 3
3 4
4 5
5 6
1 0
6 2

样例输出 3

2