● 8:Starship Troopers - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: westship (" "), 信区: ACMICPC
标题: 8:Starship Troopers
发信站: 荔园晨风BBS站 (Sat May 22 14:04:41 2004)

You, the leader of Starship Troopers, are sent to destroy a base of the bugs.
The base is built underground. It is actually a huge cavern, which consists of
many rooms connected with tunnels. Each room is occupied by some bugs, and th
eir brains hide in some of the rooms. Scientists have just developed a new wea
pon and want to experiment it on some brains. Your task is to destroy the whol
e base, and capture as many brains as possible.

To kill all the bugs is always easier than to capture their brains. A map is d
rawn for you, with all the rooms marked by the amount of bugs inside, and the
possibility of containing a brain. The cavern's structure is like a tree in su
ch a way that there is one unique path leading to each room from the entrance.
To finish the battle as soon as possible, you do not want to wait for the tro
opers to clear a room before advancing to the next one, instead you have to le
ave some troopers at each room passed to fight all the bugs inside. The troope
rs never re-enter a room where they have visited before.

A starship trooper can fight against 20 bugs. Since you do not have enough tro
opers, you can only take some of the rooms and let the nerve gas do the rest o
f the job. At the mean time, you should maximize the possibility of capturing
a brain. To simplify the problem, just maximize the sum of all the possibiliti
es of containing brains for the taken rooms. Making such a plan is a difficult
job. You need the help of a computer.

Input

The input contains several test cases. The first line of each test case contai
ns two integers N (0 < N <= 100) and M (0 <= M <= 100), which are the number o
f rooms in the cavern and the number of starship troopers you have, respective
ly. The following N lines give the description of the rooms. Each line contain
s two non-negative integers -- the amount of bugs inside and the possibility o
f containing a brain, respectively. The next N - 1 lines give the description
of tunnels. Each tunnel is described by two integers, which are the indices of
the two rooms it connects. Rooms are numbered from 1 and room 1 is the entran
ce to the cavern.

The last test case is followed by two -1's.

Output

For each test case, print on a single line the maximum sum of all the possibil
ities of containing brains for the taken rooms.

Sample Input

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

Sample Output

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店