Minimum Cost Defense on a Starship Network

A country A is preparing a series of defensive measures to protect its n starships from an attack by country B. The country has n starships that must be protected. In order to save material, the commander has connected these starships with n - 1 bidirectional accelerated channels, forming a tree structure. Each starship has two attributes, a_i and b_i, representing the population and technological level respectively, and they also serve as the cost parameters for building defense measures.

On each starship, you can choose among two types of defense measures or decide not to build any defense measure on that ship. However, you cannot build both on the same ship.

The details of the defense measures are as follows:

• Type I: If built on ship i, it costs \(a_i\) monetary units and protects ship i itself and all starships that are directly connected (i.e. at distance 1) to it.
• Type II: If built on ship i, it costs \(b_i\) monetary units and protects ship i itself and all starships which are exactly at a distance \(r\) from ship i (the distance is measured as the minimum number of accelerated channels connecting two ships). The coverage does not include starships at distances other than \(r\) (except for i itself, which is always protected).

Your goal is to determine the minimum total cost required to protect all the starships.

Note on Formulas

All formulas are written in LaTeX format. For example, the cost of a Type I defense on ship \(i\) is \(a_i\), and the cost of a Type II defense on ship \(i\) is \(b_i\).

inputFormat

The first line contains two integers \(n\) and \(r\) --- the number of starships and the specific distance for Type II defense measures.

The next \(n\) lines each contain two integers \(a_i\) and \(b_i\) \( (1 \leq i \leq n) \) representing the cost parameters for the i-th starship.

The following \(n-1\) lines each contain two integers \(u\) and \(v\) indicating a bidirectional accelerated channel connecting starship \(u\) and starship \(v\). It is guaranteed that these channels form a tree.

outputFormat

Output a single integer, the minimum monetary cost required to protect all the starships.

sample

3 1
1 2
2 1
3 3
1 2
2 3

2