#include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 typedef long long ll;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt;

 int aa[MAXN];

 int tot,head[MAXN],dp[MAXN][MAXN],in[MAXN];

 int bug[MAXN],val[MAXN],vis[MAXN];

 struct Edge

 {

     int to,next;

 }edge[MAXN<<];

 void addedge(int u,int v)

 {

     edge[tot].to=v;

     edge[tot].next=head[u];

     head[u]=tot++;

 }

 void dfs(int u)

 {

     vis[u]=;

     int num=(bug[u]+)/;

     for(int i=num;i<=m;i++) dp[u][i]=val[u];

     for(int i=head[u];i!=-;i=edge[i].next)

     {

         int v=edge[i].to;

         if(vis[v])  continue;

         dfs(v);

         for(int j=m;j>=num;j--)

         {

             for(int k=;j-k>=num;k++)    //派k人攻打其他地方

             {

                 dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);

             }

         }

     }

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

     cl(dp);

     cl(vis);

 }

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         if(n==-&&m==-)  break;

         init();

         for(i=;i<=n;i++)

         {

             scanf("%d%d",&bug[i],&val[i]);

         }

         int u,v;

         for(i=;i<=n-;i++)

         {

             scanf("%d%d",&u,&v);

             addedge(u,v);

             addedge(v,u);

         }

         if(m==)

         {

             printf("0\n");

             continue;

         }

         dfs();

         printf("%d\n",dp[][m]);

     }

 }