Problem Description

Country A is preparing to build a series of defense measures to counter the potential attack from Country B.

Country A has $n$ interstellar-class warships, which are all critical to protect. To save materials, the commander has established $n-1$ bidirectional acceleration channels connecting these warships. Each warship has two attributes $a_i$ and $b_i$, representing the population and technological level of the warship, respectively.

On each warship, there are two types of defense measures to choose from. You can choose to build one of them, neither, but not both.

Building Type I defense on the $i$-th warship requires $a_i$ currency and can protect the $i$-th warship itself and any directly connected warships.

Building Type II defense on the $i$-th warship requires $b_i$ currency and can protect the $i$-th warship itself and all warships exactly $r$ distance away from it.

The distance between warship $u$ and warship $v$ is defined as the minimum number of acceleration channels needed to travel from $u$ to $v$.

Your task is to calculate the minimum amount of currency needed to protect all warships.

Input Format

The first line contains two positive integers $n$ and $r$.

The next $n-1$ lines each contain two positive integers $u$ and $v$, indicating that there is a channel connecting warships $u$ and $v$.

The next $n$ lines, the $i$-th line contains two positive integers $a_i$ and $b_i$, representing the cost to build Type I and Type II defenses on the $i$-th warship, respectively.

Output Format

A single line containing an integer, representing the minimum amount of currency needed to protect all warships.

Sample Input and Output

Input Sample #1

1 1
1 1

Output Sample #1

1

Input Sample #2

3 2
1 2
1 3
2 1
111111 1111111
3 45

Output Sample #2

2

Input Sample #3

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

Output Sample #3

2

Notes

[Sample Explanation #1]

Building either type of defense on the $1$-th warship costs $1$ currency.

[Sample Explanation #2]

Building Type I defense on the $1$-th warship costs $2$ currency.

[Sample Explanation #3]

Building Type II defense on both the $1$-th and $2$-th warships costs $2$ currency.

[Data Range]

This problem is bundled with subtasks and uses subtask dependencies.

For $100\%$ of the data, $1 \le n \le 200$, $1 \le r \le 7$, $1 \le a_i, b_i \le {10}^9$, $1 \le u, v \le n$, and it is guaranteed that any two warships can be reached through some acceleration channels.

见题面 Input 部分

见题面 Output 部分