1 /*
 2 DP方程不好理解。不足20个bug也要安排士兵。
 3 */
 4 #include<iostream>
 5 #include<string>
 6 #include<cstdio>
 7 #include<cmath>
 8 #include<cstring>
 9 #include<algorithm>
10 #include<vector>
11 #include<iomanip>
12 #include<queue>
13 #include<stack>
14 using namespace std;
15 int n,m,lne;
16 int dp[110][110];
17 int head[110];
18 int a[110],b[110];
19 bool vis[110];
20 struct node
21 {
22     int to,next;
23 }tree[210];
24 void add(int u,int v)
25 {
26     tree[lne].to=v;
27     tree[lne].next=head[u];
28     head[u]=lne++;
29 }
30 void dfs(int root)
31 {
32     vis[root]=1;
33     for(int i=a[root];i<=m;i++)
34     dp[root][i]=b[root];//能获得b的情况下，赋值
35     for(int i=head[root];i!=-1;i=tree[i].next)
36     {
37         int son=tree[i].to;
38         if(vis[son])
39         continue;
40         dfs(son);
41         for(int j=m;j>=a[root];j--)
42         {
43             for(int k=1;k+j<=m;k++)
44             dp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[son][k]);//一共带有j+k个士兵在root点放j个士兵
45                                                                    //dp[root][j+k]是在士兵数量够用的情
46             //况下的值，当这个父亲当儿子时他就有两个值一个是此值，一个是0，当dp[son][k]中的k大于等于他
47             //需要的士兵时dp[son][k]不是0，k小于他需要的士兵时dp[son][k]取0。
48         }
49     }
50 }
51 int main()
52 {
53     int u,v;
54     while(scanf("%d%d",&n,&m))
55     {
56         if(n==-1&&m==-1)
57         break;
58         memset(dp,0,sizeof(dp));
59         memset(head,-1,sizeof(head));
60         memset(vis,0,sizeof(vis));
61         for(int i=1;i<=n;i++)
62         {
63             scanf("%d%d",&a[i],&b[i]);
64             a[i]=(a[i]+19)/20;
65         }
66         lne=0;
67         for(int i=0;i<n-1;i++)
68         {
69             scanf("%d%d",&u,&v);
70             add(u,v);
71             add(v,u);
72         }
73         if(m==0) //没有士兵不能得到价值
74         {
75             printf("0\n");
76             continue;
77         }
78         dfs(1);
79         printf("%d\n",dp[1][m]);
80     }
81     return 0;
82 }