Key to Freedom

Time Limit: 1 Second    Memory Limit: 32768 KB

Background

After got out of the horrible room, a line of words appeared, saying "Now, you have to collect enough keys to open your Gate to Freedom!"

"But we've already passed the Gate to Freedom!" I said.

"You have only passed the gate of your body, not your heart!" a strange voice came to our ears," Everybody has its own Gate to Freedom. It leads him to his new life; make him forget his past, his sadness, and when you pass your Gate to Freedom, you'll have a new start."

"How can I do that?"

"Believe in yourself, young boy. You will get it."

Problem

Keys are blocked in some boxes connected to the door. So, I have to use some power to open the box and the door. While the door is opened, I can go through the door.

There're N (N <= 100) rooms in the labyrinth connected by N-1 edges. Each room has a number of key, and the power needed to open. Now, my power is limited, how many keys I can get at most?

I'm at node 1 at first.

Input

This problem contains multiple test cases.

Each test case begins with two integers N and Power (Power <= 100), then N lines, each line has 2 numbers: costi and keyi. Next N-1 lines, every line contain 2 numbers: x, y, stands for there's a door between x and y.

Output

For each test case, output how many keys I can get at most.

Sample Input

5 5
1 2
1 1
1 1
2 3
3 4
1 2
1 3
2 4
2 5

Sample Output

7

Submit

Source: JIANG, Yanyan's Contest #2