问题描述

通向自由的钥匙被放n个房间里，这n个房间由n-1 条走廊连接。但是每个房间里都有特别的保护魔法，在它的作用下，我无法通过这个房间，也无法取得其中的钥匙。虽然我可以通过消耗能量来破坏房间里的魔法，但是我的能量是有限的。那么，如果我最先站在 1号房间（1 号房间的保护魔法依然是有效的，也就是，如果不耗费能量，我无法通过1号房间，也无法取得房间中的钥匙） ，如果我拥有的能量为P，我最多能取得多少钥匙？

输入数据

第一行包含两个非负整数，第一个为N，第二个为P。 接下来n 行 ，按1~n的顺序描述了每个房间。 第i+1行包含两个非负整数cost和 keys，分别为第i件房取消魔法需要耗费的能量和房间内钥匙的数量。 接下来 n-1行，每行两个非负整数 x,y，表示x 号房间和y号是连通的。

输出数据

一行一个整数，表示取得钥匙的最大值。

样例输入:key.in

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

输出: key.out

7

数据范围

对于 20%的测试数据，有n<=20

对于 30%的测试数据，有n<=30

对于所有测试数据，有p,n<=100, cost <= Maxint, keys<= Maxint