Protect the Pollen!

문제

The Flariana flowers and the bumblebees form one of the nicest partnerships in the rainforest. In spring, several flowers bloom and start producing pollen. Special vines form a network of bridges between the flowers. Using the vines, there is exactly one way to get from each flower to any other flower.

Every flower has a family of bees on it. This family protects all of the vines that touch that flower. This means that every vine is protected by two families. The family on flower $kk$ consists of $s_{k}s\_k$ bees and has a pollination power of $p_{k}p\_k$.

One day, a bee scout announced that there is a new flower patch over the hill and they need a group of bees to help pollinate it.

As the bee queen, you must select a set of families to send on the mission. For every vine, at least one of the two families currently protecting it must stay behind so the vine remains protected. All bees in the selected families must go. You are willing to send at most $SS$ bees on the mission in total.

Determine the largest total pollination power that you can send on the mission.

입력

The first line contains the integer $NN$ ($1\le N\le 3001\; \backslash leq\; N\; \backslash leq\; 300$), which is the number of flowers, and $SS$ ($1\le S\le 3001\; \backslash leq\; S\; \backslash leq\; 300$), which is the maximum number of bees you can send on the mission. The flowers are numbered $11$ to $NN$.

The next $NN$ lines describe the families. Each of these lines contains two integers $s_{k}s\_k$ ($1\le s_k\le 3001\; \backslash leq\; s\_k\; \backslash leq\; 300$), which is the number of bees in this family, and $p_{k}p\_k$ ($1\le p_k\le 1001\; \backslash leq\; p\_k\; \backslash leq\; 100$), which is the pollination power of this family.

The last $N-1N-1$ lines describe the vines.  Each of these lines contains two distinct integers $uu$ ($1\le u\le N1\; \backslash leq\; u\; \backslash leq\; N$) and $vv$ ($1\le v\le N1\; \backslash leq\; v\; \backslash leq\; N$), indicating that there is a vine between flowers $uu$ and $vv$.

출력

Display the largest total pollination power that you can send on the mission.

5 10
2 1
2 2
2 4
2 8
2 16
1 2
2 3
3 4
4 5

21

7 10
1 7
2 4
5 18
2 3
3 12
9 20
2 8
1 2
1 3
2 4
2 5
3 6
3 7

33