#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <cctype>

#include <vector>

#include <iterator>

#include <set>

#include <map>

#include <sstream>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define spf sprintf

#define pb push_back

#define debug printf("!\n")

#define MAXN 1010

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#define LL long long

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define pqueue priority_queue

#define INF 0x3f3f3f3f

int n,m;

struct node

{

    int y,next;

}tree[];

int head[],dp[][],ptr=;

int bug[],vl[],vis[];

void add(int x,int y)

{

    tree[ptr].y = y;

    tree[ptr].next = head[x];

    head[x] = ptr++;

}

void dfs(int root)

{

    int i,j,k;

    vis[root] = ;

    int cost = (bug[root]+)/;

    for(i=cost;i<=m;i++)

        dp[root][i] = vl[root];

    for(i=head[root]; i!=-; i=tree[i].next)

    {

        int p = tree[i].y;

        if(!vis[p])

        {

            dfs(p);

            for(j=m;j>=cost;j--)

            {

                for(k=;j+k<=m;k++)

                {

                    dp[root][j+k] = max(dp[root][j+k],dp[p][k]+dp[root][j]);

                }

            }

        }

    }

}

int main()

{

    int i,j,k,a,b;

    while(~sf("%d%d",&n,&m) && m+n>)

    {

        mem(head,-);

        ptr = ;

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

        {

            sf("%d%d",&bug[i],&vl[i]);

        }

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

        {

            sf("%d%d",&a,&b);

            add(a,b);

            add(b,a);

        }

        if(!m)

        {

            pf("0\n");

            continue;

        }

        mem(dp,);

        mem(vis,);

        dfs();

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

    }

    return ;

}

/*

5 10

50 10

40 10

40 20

65 30

70 30

1 2

1 3

2 4

2 5

1 1

20 7

-1 -1

*/