
118  ZOJ Monthly, July 2012  E
Akiba is a dangerous country since a bloodsucker living there. Sometimes the bloodsucker will appear and kill everyone who isn't at his hometown. One day, a brave person named CC finds a treasure map, and he wants to get as much as possible. Akiba consists of n towns and n1 roads. There is a way from each town to any other. Each town contains some treasure values V_{i}. CC starts from town k(his hometown), at day 0. After m days, the bloodsucker will appear and CC would be killed if he hasn't been back yet, it means CC has m days for hunting the treasure at most. It takes CC T_{i} days to move from one town to another neighbour town.(Two towns called neighbour if they are the endpoint of one road.) You can assume CC will get the treasure immediately as he arrives at that town. CC wants to obtain as much value as possible, keeping him alive at the same time. Input
There are multiple cases, about 50 cases.
1<=n<=100, 0<=V_{i}<=1000 , 1<=T_{i}<=10 OutputJust output the max value CC can get, and you should keep CC alive after m days. Sample Input2 1 3 1 2 1 1 2 2 1 3 2 1 1 2 1 2 3 3 1 2 1 2 5 Sample Output4 3 6 Hint
Sample 1: CC can go to town 2 and return at day 2. Author: LI, Chao 