ZOJ Problem Set - 1611
It is in the year of 3114. Bernie lives on moon. This summer his younger sister Rosie will come to see him. Bernie is very excited about this because he hasn't seen his lovely sister for years! So, he decides to take his little sister to travel around solar system. He soon asks The Department of Traveling on moon for a list of trips available this summer.
Then he tells his little sister about this and asks for her opinion. But to
his surprise, she wants to travel as muuuuuuch as poooooooooossible since this
summer she's gonna have a three-month holiday, and has already done all the
tasks her professor had assigned to her! Poor Bernie doesn't have a lot of pocket
money and cannot afford all the trips available in the list. So, he asks Rosie
which ones she likes best. And this is her reply:
From the first trip in the list, one by one sequentially,
Eh.., for the naughty Rosie, the preference above maybe somehow seems unreasonable. Don't care, you just take it. In order to make full use of his money, he needs to find out the trips that satisfy her most. But poor Bernie is really busy these days. So he asks you, the best friend of him, to help him. Of cause you will receive a big bonus after they finishes the memorable trips with the help of your excellent job.
The very first line of the input represent the number of test cases it has. And there are three parts for each test case.
The first part contains only one line, there is an integer T (0 < T <= 5000), follow by a string of "RMB", represent the total pocket money Bernie has. The second part represents the trips available this summer. The first line of this part contains an integer N (0 < N <= 9), which represents the number of destinations available. The rest of the second part contains N blocks, which specify the trips available for each destination. The first line of the block contains an integer K (0 < K <= 10), which represents the number of different trips to this destination. The next K lines of the block, of cause, specify the details of each trip. And each line has an integer D (0 < D <= 10), represents the length of the trip, followed by a string of "days", and an integer C (0 < C <= 300), which represents the cost of that trip, followed by a string of "RMB".
Finally, here comes the second part of each test case. There are several lines in this part, each contains an integer P (0 < P <= 120), represents the preference of Rosie for a certain trip. The preferences are listed one by one according to the trips listed above in the second part of each case sequentially, discard the notation "%" and treat it as an integer.
Your job is to select some trips, so that Bernie could afford it and also the sum of the preferences is the biggest. For each test case, just output two integers S and H (separated by a single space) in a single line, which represent how much money he should spend according to your plan, and how much 'preference' he could get.
Note: you can assume that the holiday is long enough so that they could finish all the trips available. Never mind to make out a plan of traveling to a certain destination several times because she likes it! But remember that after they finish a certain trip, the preference of that trip becomes 0 immediately, since make the same traveling is extremely boring.
Note: for the second case, one of the best selections is traveling to Mars for 3 days, and Jupiter for 4 days, and Pluto for 1 day, 2 days, and 3 days.
Source: ZOJ Monthly, May 2003