宿命 | Regulation of Destiny

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 第一行，两个正整数 $n, r$。 接下来 $n-1$ 行，每行两个正整数 $u, v$，代表一条通道所连接的两艘战舰编号为 $u, v$。 接下来 $n$ 行，第 $i$ 行两个正整数 $a_i, b_i$，分别表示在 $i$ 号战舰上建设 I 类和 II 类防御措施所需要的金钱。 ## Output 一行，一个整数，表示保护所有战舰需要的最少金钱。 [samples] ## Background 压抑是有实质的，从躯壳到内脏，密不透风地包裹，药物仅仅像缝隙里挤进去的一滴水，浇不灭深幽的火焰。 时间治愈不了一切，它只把泥泞日复一日地堆积。她的眼睛没有焦点，偶尔仿佛睡梦中惊醒，喊我的名字。 街道乱糟糟，各家店铺放着音乐，公交车轮胎碾过柏油路，小孩打闹，玻璃瓶砸碎，电瓶车相撞……但我清楚地听见自己的呼吸声。后视镜里，我又一次看到她没有焦点的眼神，裹住眼球的眼泪，水的表面张力“嗒”的一声失效。 撕开雨天，潜入他乡，所向往的尽头是天堂。 浅蓝天光，云层泛紫，微弱的灯光嵌进夕阳。 ---- “…你知道吗，所谓的力量，其实，就是心中的执念。” “执念？” “是啊…就是，必须要做的事，必须守护的人，必须…” “实现的心愿。” “那么…你心中有这样的执念吗？” “呃……有啊！我的执念，就是保护姐姐！” “傻小子，想保护你姐，等下辈子再说吧” ## Note **【样例解释 \#1】** 在 $1$ 号战舰上建设任意一种防御措施，所花金钱为 $1$。 --- **【样例解释 \#2】** 在 $1$ 号战舰上建设 I 类防御措施，所花金钱为 $2$。 --- **【样例解释 \#3】** 在 $1,2$ 号战舰上各建设一个 II 类防御措施，所花金钱为 $2$。 ------------ **【数据范围】** **本题采用捆绑测试且使用子任务依赖。** | 子任务编号 | $n \le$ | $r \le$ | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | | 1 | $10$ | $5$ | 5 | | 2 | $200$ | $1$ | 5 | | 3 | $20$ | $7$ | 10 | | 4 | $100$ | $2$ | 8 | | 5 | $100$ | $4$ | 11 | | 6 | $100$ | $5$ | 8 | | 7 | $200$ | $6$ | 34 | | 8 | $200$ | $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$，保证任意两艘战舰可以通过若干条加速通道到达。