Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1611
Traveling in Solar System

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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.

Trip-ID Destination Length(days) Cost(RMB)
1001 Mars 2 155
1002 Mars 3 170
1003 Jupiter 4 180
1004 Jupiter 5 220
1005 Pluto 1 230
1006 Pluto 2 250
1007 Pluto 3 270
1008 Pluto 4 380

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,

Trip-ID 1001 1002 1003 1004 1005 1006 1007 1008
Preference 30% 70% 75% 65% 110% 100% 90% 120%

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.

Sample Input


150 RMB
Neptune 1
1 days 100 RMB
Earth 1
1 days 60 RMB

1153 RMB
Mars 2
2 days 155 RMB
3 days 170 RMB
Jupiter 2
4 days 180 RMB
5 days 220 RMB
Pluto 4
1 days 230 RMB
2 days 250 RMB
3 days 270 RMB
4 days 380 RMB

Sample Output

100 90
1100 445

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.

Author: Bernie.H
Source: ZOJ Monthly, May 2003
Submit    Status