3193. 键盘

单点时限: 2.0 sec

内存限制: 256 MB

有一些电脑需要配置键盘,有的电脑只有USB接口,有的只有PS/2接口,而另一些两种接口都有。

现有m个键盘,已知每个键盘的价格和类型。要求如下:1)给尽可能多的电脑配上键盘;2)在满足条件1的情况下,花费尽可能少。

输入格式

第 $1$ 行:整数 $T$ ($1 \le T \le 10$) 为问题数。

第一个问题的数据按如下格式输入:

第2行:三个整数$a,b,c(0≤a,b,c≤100)$,分别表示只有USB接口,只有PS/2接口,两种接口都有的电脑台数。

第3行:一个整数$m(1≤m≤300)$,表示现有键盘的个数。

接下来m行,每行有一个整数p表示价格$(1≤p≤200)$和一个字符串表示键盘的类型,两者之间用一个空格分开。(注意:每行所列的键盘均表示只有1个)

后面问题的数据,格式与第一个问题相同。

输出格式

对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0: 等);然后在一行中输出两个数字,第一个表示最多可以给多少个电脑配上键盘,第二个表示最少要花多少钱,两者之间用一个空格分开。

样例

Input
3
2 1 1
4
5 USB
6 PS/2
3 PS/2
7 PS/2
3 0 3
9
3 USB
8 USB
6 PS/2
16 USB
11 USB
14 PS/2
8 USB
5 PS/2
19 USB
0 5 5
10
3 USB
9 USB
10 PS/2
7 USB
15 PS/2
14 PS/2
12 USB
13 PS/2
3 USB
7 USB
Output
case #0:
3 14
case #1:
6 41
case #2:
9 81

345 人解决,386 人已尝试。

459 份提交通过,共有 1003 份提交。

1.6 EMB 奖励。

创建: 3 年,5 月前.

修改: 2 年前.

最后提交: 1 周,1 天前.

来源: N/A

题目标签