题目描述
给一棵 $n$ 个点的树，每个点有两个权值 $a_i, b_i$。对于树上的一条简单路径，若这条路径上 $b$ 之和乘上 $a$ 的最小值大于等于一个常数 $V$，那么这条路径被称作一条好的路径。
即：对于一条简单路径，设 $p_1, p_2, \dots, p_k$ 为路径上的点。这条简单路径是好的，当且仅当 $\min_{i=1}^k a_{p_i} \times \sum_{i=1}^k b_{p_i} \ge V$。
求所有好的路径中，$\sum b$ 的最小值。
输入格式
第一行两个整数 $n, V$。
接下来 $n$ 行每行两个整数 $a_i, b_i$。
接下来 $n-1$ 行每行两个整数 $x_i, y_i$，表示一条树边。
输出格式
一行一个整数表示答案。
样例
样例 0 输入
10 100 4 8 7 6 4 6 5 5 4 4 7 4 5 4 8 8 5 5 6 4 1 8 1 2 2 3 2 6 10 9 4 1 4 9 5 7 5 4
样例 0 输出
25
样例 1 输入/输出
见附加文件 series1.in/series1.out，该样例满足子任务一的限制。
样例 2 输入/输出
见附加文件 series2.in/series2.out，该样例满足子任务二的限制。
样例 3 输入/输出
见附加文件 series3.in/series3.out，该样例满足子任务三的限制。
样例 4 输入/输出
见附加文件 series4.in/series4.out，该样例满足子任务四的限制。
样例 5 输入/输出
见附加文件 series5.in/series5.out，该样例满足子任务五的限制。
样例 6 输入/输出
见附加文件 series6.in/series6.out，该样例满足子任务六的限制。
子任务
对于所有测试点均满足 $1 \le V \le 10^{18}$，$1 \le a_i, b_i \le 10^9$。数据保证有解。
| 子任务编号 | $n \le$ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $2 \times 10^3$ | 无 | $15$ |
| $2$ | $10^4$ | $15$ | |
| $3$ | $2 \times 10^5$ | 存在一个点度数为 $n-1$ | $15$ |
| $4$ | 第 $i$ 条边连接 $i$ 和 $i+1$ | $15$ | |
| $5$ | $5 \times 10^4$ | 无 | $20$ |
| $6$ | $2 \times 10^5$ | $20$ |