Description

A 国为了防御 B 国的进攻，准备兴建一系列防御措施。

A 国有 $n$ 艘恒星级战舰，这些战舰无论如何都是要被保护的。为了节省材料，总司令用了 $n-1$ 条双向加速通道将这些战舰连接了起来。每个战舰有两个属性 $a_i,b_i$，分别代表战舰的人口数，科技程度。

在每艘战舰上有两种防御措施可以选择。你可以选择建设其中的一种，也可以选择不建设，但不能两种都建设。

在 $i$ 号战舰上建设 I 类防御措施需要 $a_i$ 的金钱，可以保护 $i$ 号战舰本身和与其直接相连的战舰。

在 $i$ 号战舰上建设 II 类防御措施需要 $b_i$ 的金钱，可以保护 $i$ 号战舰本身以及所有与 $i$ 号战舰的距离恰好为 $r$ 的战舰。

定义战舰 $u$ 和战舰 $v$ 的距离为从 $u$ 到 $v$ 需要经过最少多少条加速通道。

现在，请你求出保护所有战舰需要的最少金钱。

Input Format

第一行，两个正整数 $n, r$。

接下来 $n-1$ 行，每行两个正整数 $u, v$，代表一条通道所连接的两艘战舰编号为 $u, v$。

接下来 $n$ 行，第 $i$ 行两个正整数 $a_i, b_i$，分别表示在 $i$ 号战舰上建设 I 类和 II 类防御措施所需要的金钱。

Output Format

一行，一个整数，表示保护所有战舰需要的最少金钱。

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

【样例解释 #1】

在 $1$ 号战舰上建设任意一种防御措施，所花金钱为 $1$。

【样例解释 #2】

在 $1$ 号战舰上建设 I 类防御措施，所花金钱为 $2$。

【样例解释 #3】

在 $1,2$ 号战舰上各建设一个 II 类防御措施，所花金钱为 $2$。

【数据范围】

本题采用捆绑测试且使用子任务依赖。

对于 $100\%$ 的数据，$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$，保证任意两艘战舰可以通过若干条加速通道到达。