#include <iostream>
#include <vector>
#include <queue>
#define MAXN 111
using namespace std;
#define MAX(a, b) a>b?a:b

int val[MAXN][ 2 ];
int dp[MAXN][MAXN];
int n , c;
bool vist[MAXN];

struct ver {

    int v;
    int next;
};

ver e[MAXN*2];
int p[MAXN], aid;

void add(int a, int b) {

    e[aid].next = p[ a ];
    e[aid].v = b;
    p[ a ] = aid ++;

    swap(a, b);

    e[aid].next = p[ a ];
    e[aid].v = b;
    p[ a ] = aid ++;
} 

//dp[ i ][ k ]  表示以i為根節(jié)點用了k個人去消滅蟲的最大值
//dp[ 1 ][ c ]  為結(jié)果
//當trooper = 0 時, 即使不花費任何代價也拿不了, 和背包搞混了, 杯具

void dfs (int x) {

    int i, j, k;
    int num = (val[ x ][ 0 ] + 19) / 20;
    for(i = num; i <= c; ++ i) {
    
        dp[ x ][ i ] = val[ x ][ 1 ];
    }

    vist[ x ] = true;

    for(i = p[ x ]; i != -1; i = e[ i ].next) { 
    
        int y = e[ i ].v;

        if(vist[ y ]) continue;
        
        dfs (y);   

        for(j = c; j >= num; -- j) {
        
            for(k = 1; j + k <= c; ++ k) {
            
                if(dp[ y ][ k ]) {
                
                    dp[ x ][j + k] = MAX(dp[ x ][j + k], dp[ x ][ j ] + dp[ y ][ k ]);
                }
            }
        }
    }
}

int main() {
    
    int i, m;
    while(cin >> n >> c) {
        
        if(n == -1 && c == -1) break;

        memset(dp, 0, sizeof(dp));
        memset(vist, false, sizeof(vist));
        memset(p, -1, sizeof(p));
        aid = 0;

        for(i = 1; i <= n ; ++ i) {
            
            cin >> val[ i ][ 0 ] >> val[ i ][ 1 ];
        }
        
        m = n;
        while(-- m) {
            
            int a, b;
            cin >> a >> b;
            
            add(a, b);
        }

        if(c == 0) {
        
            cout << 0 << endl;
            continue;
        }

        dfs (1);

        cout << dp[ 1 ][ c ] << endl;
    }
    return 0;
}