1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <math.h>
11 #include <stdlib.h>
12 #include <time.h>
13 #define MP(a, b) make_pair(a, b)
14 #define PB(a) push_back(a)
15 using namespace std;
16 
17 const int LEN = 2010;
18 int W[LEN], V[LEN], n, m, dp[LEN][LEN];
19 vector<int> Map[LEN];
20 
21 void dfs(int v, int fa){
22     for(int i=0; i<Map[v].size(); i++){
23         int x = Map[v][i];
24         if(x != fa){
25             dfs(x, v);
26             for(int k=m; k>=V[v]; k--){
27                 for(int j=1; j<=m; j++){
28                     if(k>=j+V[v])dp[v][k] = max(dp[v][k], dp[v][k-j] + dp[x][j]);
29                 }
30             }
31         }
32     }
33     for(int i=V[v]; i<=m; i++) dp[v][i] += W[v];
34 }
35 
36 int main()
37 {
38 //    freopen("in.txt","r",stdin);
39     //freopen("out.txt","w",stdout);
40 
41     int a, b;
42     while(cin >> n >> m){
43         if(n < 0 && m < 0) break;
44         for(int i=0; i<LEN; i++) Map[i].clear();
45         memset(dp, 0, sizeof dp);
46         for(int i=0; i<n; i++){
47             cin >> V[i] >> W[i];
48             V[i] = (V[i]+19)/20;
49         }
50         for(int i=0; i<n-1; i++){
51             cin >> a >> b;
52             a--, b--;
53             Map[a].PB(b);
54             Map[b].PB(a);
55         }
56         dfs(0, -1);
57         if(!m) cout << 0 << endl;
58         else cout << dp[0][m] << endl;
59     }
60     return 0;
61 }