2172: 宝典2第十一章商店购物

【题目描述】商店购物(shopping2.cpp/c/pas) USACO3.3.2

魔法商店中每种商品都有一个价格。例如，一朵花的价格是2 元，一个花瓶的价格是5 元。为了吸引更多的顾客，商店提供了特殊优惠价。

特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如：3朵花的价格不是6元而是5 元；2个花瓶加1朵花是10 元不是12元。

编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为3朵花和2个花瓶。那么顾客应付款为14 元。因为1朵花加2个花瓶的优惠价为10元；2朵花的正常价为4元。

【输入格式】

    输入文件包括一些商店提供的优惠信息，接着是购物清单。

　　第一行为优惠商品的种类数（0≤ s ≤ 99）。

　　第二行到第s+1 行，每一行都用几个整数来表示一种优惠方式。第一个整数 n （1 ≤ n ≤ 5），表示这种优惠方式由 n 种商品组成。后面 n 对整数 c 和 k 表示 k （1≤ k ≤5）个编号为 c （1≤ c ≤ 999）的商品共同构成这种优惠，最后的整数 p 表示这种优惠的优惠价（1≤ p ≤ 9999）。优惠价总是比原价低。

　　第 s+2 行，这一行有一个整数 b （0≤ b ≤5），表示需要购买 b 种不同的商品。

　　第 s+3 行…第 s+b+2 行，这 b 行中的每一行包括三个整数：c ，k和 p 。c 表示唯一的商品编号（1 ≤ c ≤ 999），k 表示需要购买的 c 商品的数量（1≤k ≤5）。p 表示 c 商品的原价（1 ≤ p≤ 999）。最多购买 5×5=25 个商品。

　　【输出格式】

只有一行，输出一个整数：购买这些商品的最低价格。

【输入样例】

2

1 7 3 5

2 7 1 8 2 10

2

7 3 2

8 2 5

【输出样例】

14