Given a tree with $n$ nodes, each node has two weights $a_i$ and $b_i$. A simple path on the tree is called a "good path" if the sum of $b$ values on the path multiplied by the minimum $a$ value on the path is greater than or equal to a constant $V$.

That is, for a simple path with nodes $p_1, p_2, \dots, p_k$, the path is good if and only if $\min_{i=1}^k a_{p_i} \times \sum_{i=1}^k b_{p_i} \ge V$.

Find the minimum $\sum b$ among all good paths.

Input

The first line contains two integers $n$ and $V$.

The next $n$ lines each contain two integers $a_i$ and $b_i$.

The next $n-1$ lines each contain two integers $x_i$ and $y_i$, representing an edge in the tree.

Output

Output a single integer representing the answer.

Examples

Input 1

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

Output 1

25

See additional file series1.in/series1.out, this sample satisfies the constraints of subtask 1.

See additional file series2.in/series2.out, this sample satisfies the constraints of subtask 2.

See additional file series3.in/series3.out, this sample satisfies the constraints of subtask 3.

See additional file series4.in/series4.out, this sample satisfies the constraints of subtask 4.

See additional file series5.in/series5.out, this sample satisfies the constraints of subtask 5.

See additional file series6.in/series6.out, this sample satisfies the constraints of subtask 6.

Subtasks

For all test cases, $1 \le V \le 10^{18}$ and $1 \le a_i, b_i \le 10^9$. It is guaranteed that a solution exists.