采购计划问题

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

有一个从事环保行业的公司出售4中型号的家用节能荧光灯泡。这些灯泡的价格很高,但是寿命比一般的灯泡要长,耗能也比一般的灯泡要少。为了扩大销量,厂家推出了优惠套装,每个套装里含有不同型号的灯泡若干个。一个套装的价格一般比它里面所有灯泡的单价的总和要便宜。顾客通常想买若干个不同型号的灯泡。现在请你写一个程序求出能满足顾客要求的最低价格的购买方案。

Input

输入数据分为两部分,第1部分给出所有套装的详细信息。第2部分是顾客的购买需求。4种型号的灯泡分别用字母“a”,“b”,“c”,“d”表示。

第1部分的第1行是一个整数n(1<=n<=50),表示有n个优惠套装。接着有n行,每一行描述一个套装的信息,首先是套装的标号(整数),接着是套装的价格(正实数),再跟着的是套装里不同型号灯泡的相应的数目。每种型号至少描述一次,并且没有固定顺序,以“型号 数量“的形式表示。

例如:“210 76.95 c 1 a 3 d 4”表示该套装的标号为210,价格为76.95,有3个a型灯泡,1个c型灯泡,4个d型灯泡,没有b型灯泡。

第2部分只有一行,描述顾客要买的不同型号灯泡的相应数目,格式与描述套装所含灯泡情况的方法相同。如:“b 3 a 1 d 2”表示顾客要买1个a型灯泡,3个b型灯泡,2个d型灯泡。

Output

第1行输出购买方案的最小费用,保留两位小数。

第2行按套装标号从小到达依次输出要购买的套装的标号。

如果某套装的购买数目多于1,则在标号后用“(数量)”表示。各个套装标号间用一个空格隔开。

Sample Input

5
10 25.00 b 2
502 17.95 a 1
3 13.00 c 1
55 27.50 b 1 d 2 c 1
6 52.87 a 2 b 1 d 1 c 3
b 3 c 3 d 3 a 1

Sample Output

100.45
55(3) 502

Hint

Source