编程介的小学生 2017-03-09 02:16 采纳率: 0.2%
浏览 836
已采纳

Traveling in Solar System

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

展开全部

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-03-15 09:22
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)
编辑
预览

报告相同问题?

悬赏问题

  • ¥15 关于#c##的问题:treenode反序列化后获取不到上一节点和下一节点,Fullpath和Handle报错
  • ¥15 一部手机能否同时用不同的app进入不同的直播间?
  • ¥15 没输出运行不了什么问题
  • ¥20 输入import torch显示Intel MKL FATAL ERROR,系统驱动1%,: Cannot load mkl_intel_thread.dll.
  • ¥15 点云密度大则包围盒小
  • ¥15 nginx使用nfs进行服务器的数据共享
  • ¥15 C#i编程中so-ir-192编码的字符集转码UTF8问题
  • ¥15 51嵌入式入门按键小项目
  • ¥30 海外项目,如何降低Google Map接口费用?
  • ¥15 fluentmeshing