Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
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.

Input

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.

Output

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

2

150 RMB
2
Neptune 1
1 days 100 RMB
Earth 1
1 days 60 RMB
90
80

1153 RMB
3
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
30
70
75
65
110
100
90
120

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