Background

Oppression has substance. From the shell to the organs, it wraps tightly with no air getting through. Medicine is only like a drop of water squeezed into a crack, unable to put out the deep, hidden flame.

Time cannot heal everything. It only piles up the mud day after day. Her eyes have no focus. Sometimes it is as if she wakes up from a dream in shock and calls my name.

The street is a mess. Every shop is playing music. Bus tires roll over the asphalt road. Kids are fooling around. Glass bottles shatter. Electric scooters collide... but I can clearly hear my own breathing. In the rearview mirror, I once again see her unfocused stare, tears wrapping around her eyeballs, and the surface tension of the water fails with a “da” sound.

Tear open the rainy day, dive into a foreign land, and the end one longs for is heaven.

Pale blue daylight, purple clouds, weak lights embedded into the sunset.

“...Do you know? What people call power is actually the obsession in one’s heart.”

“Obsession?”

“Yeah... it’s, the things you must do, the people you must protect, you must...”

“A wish that has to come true.”

“Then... do you have such an obsession in your heart?”

“Uh... yes! My obsession is protecting my sister!”

“Silly kid. If you want to protect your sister, talk about it in your next life.”

Problem Description

Country $A$ is preparing to build a series of defensive measures to guard against an attack from Country $B$.

Country $A$ has $n$ stellar-class battleships, and these battleships must be protected no matter what. To save materials, the commander-in-chief connected these battleships using $n - 1$ bidirectional acceleration channels. Each battleship has two attributes $a_i, b_i$, representing the battleship’s population and technology level.

On each battleship, there are two types of defensive measures you can choose from. You may build one of them, or build nothing, but you cannot build both.

Building a Type I defense on battleship $i$ costs $a_i$ money, and it can protect battleship $i$ itself and the battleships directly connected to it.

Building a Type II defense on battleship $i$ costs $b_i$ money, and it can protect battleship $i$ itself and all battleships whose distance from battleship $i$ is exactly $r$.

The distance between battleship $u$ and battleship $v$ is defined as the minimum number of acceleration channels that need to be passed through to go from $u$ to $v$.

Now, find the minimum amount of money required to protect all battleships.

Input Format

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

The next $n - 1$ lines each contain two positive integers $u, v$, indicating that the channel connects battleships $u$ and $v$.

The next $n$ lines: the $i$-th line contains two positive integers $a_i, b_i$, representing the money needed to build a Type I defense and a Type II defense on battleship $i$, respectively.

Output Format

One line containing one integer, the minimum amount of money required to protect all battleships.

1 1
1 1

1

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

2

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

2

Hint

Sample Explanation #1

Building any type of defensive measure on battleship $1$ costs $1$.

Sample Explanation #2

Build a Type I defense on battleship $1$, costing $2$.

Sample Explanation #3

Build one Type II defense on each of battleships $1$ and $2$, costing $2$.

Constraints

This problem uses bundled testdata and subtask dependency.

For $100\%$ of the testdata, $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$. It is guaranteed that any two battleships can reach each other through some acceleration channels.

Translated by ChatGPT 5