题目背景

压抑是有实质的，从躯壳到内脏，密不透风地包裹，药物仅仅像缝隙里挤进去的一滴水，浇不灭深幽的火焰。

时间治愈不了一切，它只把泥泞日复一日地堆积。她的眼睛没有焦点，偶尔仿佛睡梦中惊醒，喊我的名字。

街道乱糟糟，各家店铺放着音乐，公交车轮胎碾过柏油路，小孩打闹，玻璃瓶砸碎，电瓶车相撞……但我清楚地听见自己的呼吸声。后视镜里，我又一次看到她没有焦点的眼神，裹住眼球的眼泪，水的表面张力“嗒”的一声失效。

撕开雨天，潜入他乡，所向往的尽头是天堂。

浅蓝天光，云层泛紫，微弱的灯光嵌进夕阳。

---

“…你知道吗，所谓的力量，其实，就是心中的执念。”

“执念？”

“是啊…就是，必须要做的事，必须守护的人，必须…”

“实现的心愿。”

“那么…你心中有这样的执念吗？”

“呃……有啊！我的执念，就是保护姐姐！”

“傻小子，想保护你姐，等下辈子再说吧”

题目描述

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$ 需要经过最少多少条加速通道。

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

输入格式

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

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

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

输出格式

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

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

提示

【样例解释 #1】

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

---

【样例解释 #2】

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

---

【样例解释 #3】

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

---

【数据范围】

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

子任务编号	$n \le$	$r \le$	分值
1	$10$	$5$	5
2	$200$	$1$
3	$20$	$7$	10
4	$100$	$2$	8
5		$4$	11
6		$5$	8
7	$200$	$6$	34
8		$7$	19

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