14118 - Shopping Offers 商店购物

在商店中，每一种商品都有一个价格（用整数表示）。为了吸引顾客，商店推出了促销活动，将一种或多种商品组合起来以优惠价销售。

例如：

• 三朵花的价格是 5z 而不是 6z；
• 两个花瓶和一朵花的价格是 10z 而不是 12z。

现在，顾客需要购买一定数量的商品，请计算在充分利用这些优惠活动的情况下，最少需要花费多少钱。

注意：你不能为了获得更低的优惠价而额外添加不需要的商品，只能购买指定的商品，但可以自由选择使用哪些优惠（可以多次使用同一优惠，只要购买数量足够）。

输入文件包括两部分：商店提供的优惠信息和顾客的购物清单。

• 第一行包含一个整数 s（0 <= s <= 99），表示优惠方案的种类数。
• 接下来 s 行，每行描述一种优惠方案：
  • 第一个整数 n（1 <= n <= 5），表示该优惠由 n 种商品组成。
  • 后面跟着 n 对整数 c 和 k（1 <= k <= 5），表示该优惠包含 k 个编号为 c 的商品。
  • 最后一个整数 p（1 <= p <= 9999），表示该优惠的价格（优惠价一定低于原价总和）。
• 接下来一行包含一个整数 b（0 <= b <= 5），表示顾客需要购买 b 种不同的商品。
• 接下来 b 行，每行描述一种需要购买的商品：
  • 三个整数 c、k 和 p：分别表示商品编号（1 <= c <= 999）、需要购买的数量（1 <= k <= 5）以及该商品的原价（1 <= p <= 999）。

注意：总购买数量不超过 5 * 5 = 25 个商品。

输出一个整数，表示购买这些商品所需的最低总花费。

样例说明

• 优惠方案1：购买 3 个编号为 7 的商品，优惠价为 5。
• 优惠方案2：购买 1 个编号为 7 的商品和 2 个编号为 8 的商品，优惠价为 10。
• 购物清单：需要购买 3 个编号为 7 的商品（原价每个 2）和 2 个编号为 8 的商品（原价每个 5）。

最优方案：

1. 使用优惠方案2，购买 1 个 7 号和 2 个 8 号，花费 10。
2. 再以原价购买剩余的 2 个 7 号商品，花费 2×2 = 4。 总花费为 10 + 4 = 14。

数据范围与约定

• s：优惠方案数， 0 ≤ s ≤ 99 。
• 每个优惠方案包含的商品种类数 n： 1 ≤ n ≤ 5。
• 每种商品在一个优惠方案中的数量 k： 1 ≤ k ≤ 5。
• 商品编号 c： 1 ≤ c ≤ 999。
• 优惠价格 p：1 ≤ p ≤ 9999。
• 需要购买的商品种类数 b：0 ≤ b ≤ 5。
• 每种需要购买的商品数量 k：1 ≤ k ≤ 5。
• 商品原价 p：1 ≤ p ≤ 999。
• 总商品数量最多为 5×5 = 25 个。

USACO