import java.util.*;

 import static java.lang.Math.*;

 class Graph{

     ArrayList<ArrayList<Integer>> e;

     int dp[][];

     boolean vis[];

     int n,m;

     public Graph(int n,int m){

         e = new ArrayList<ArrayList<Integer>>();

         for(int i=0;i<=n;i++){

             e.add(new ArrayList<Integer>());

         }

         dp = new int[n+1][m+1];

         vis = new boolean[n+1];

         this.n = n;

         this.m = m;

     }

     public void add_edge(int from,int to){

         ArrayList<Integer> t = e.get(from);

         t.add(to);

     }

     public int dfs(int u){

         if( vis[u] ) return 0;

         vis[u] = true;

         ArrayList<Integer> t = e.get(u);

         for(int i=m;i>=Main.w[u];i--) dp[u][i] = Main.v[u];

         for(int s:t ){

             if( vis[s] ) continue;

             dfs(s);

             for(int i=m;i>=Main.w[u];i--){

                 for(int j=1;j<=m;j++){

                     if( i+j<=m ){

                         dp[u][i+j] =max(dp[u][i+j], dp[u][i]+dp[s][j]);

                     }

                 }

             }

         }

         return dp[u][m];

     }

 }

 public class Main{

     static int N,M;

     static Scanner sc = new Scanner(System.in);

     static int w[],v[];

     public static void main(String[] args){

         while( sc.hasNext() ){

             N = sc.nextInt();

             M = sc.nextInt();

             if( N==-1 && M==-1 ) break;

             w = new int[N+1];

             v = new int[N+1];

             Graph g = new Graph(N,M);

             for(int i=1;i<=N;i++){

                 w[i] = sc.nextInt();

                 v[i] = sc.nextInt();

                 w[i] = (w[i]+19)/20;

             }

             for(int i=1;i<N;i++){

                 int a = sc.nextInt();

                 int b = sc.nextInt();

                 g.add_edge(a,b);

                 g.add_edge(b,a);

             }

             if( M==0 ){

                 System.out.println(0);

                 continue;

             }

             int ans = g.dfs(1);

             System.out.println(ans);

         }

     }

 }