#include <cstdio> #include <cstring> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int inf = 1000000; const int maxn = 105; struct node{ int to,next; }tree[maxn*2]; int len,head[maxn],n,m,w[maxn],pos[maxn],temp[maxn]; void init(){ memset(head,-1,sizeof(head)); len = 0; } void add_eadge(int u,int v){ tree[len].to = v; tree[len].next = head[u]; head[u] = len++; } int d[maxn][maxn]; void dfs(int root,int f){ for(int i=0;i<w[root];i++) d[root][i] = 0; for(int j=w[root];j<=m;j++) d[root][j] = pos[root]; for(int i =head[root];i!=-1;i=tree[i].next){ if(tree[i].to==f) continue; int p = tree[i].to; dfs(p,root); for(int j=0;j<=m;j++) temp[j]=d[root][j]; for(int j=w[root]+1;j<=m;j++) for(int k=1;k+w[root]<=j;k++){ d[root][j] = max(d[root][j],d[p][k]+temp[j-k]); } } } int main() { while(scanf("%d %d",&n,&m)==2){ if(n==-1) break; init(); for(int i=1;i<=n;i++){ int x,y; scanf("%d %d",&x,&y); w[i] = x/20 + (x%20==0 ? 0:1); pos[i] = y; } for(int i=1;i<n;i++){ int x,y; scanf("%d %d",&x,&y); add_eadge(x,y); add_eadge(y,x); } if(n==0 || m==0){ printf("0\n"); continue; } dfs(1,-1); printf("%d\n",d[1][m]); } return 0; }