TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1903
  • 問題
  • P1903【S2状态压缩】商品促销
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    在一个商店里每种商品都有一个价格。比如:一束鲜花的价格是2元,一个花瓶的价格是5元。为了吸引更多的顾客,该商店推出了一些优惠促销活动。
    一种优惠是一次购买多个商品可以获得减价。比如,3束鲜花只要5元而不是6元,两个花瓶和一束鲜花只要10元而不是12元。
    请你写一个程序帮助顾客计算享受优惠后,他需要支付的费用,顾客们总是选择最佳的优惠,所以,应该使费用尽可能的低。但是你不能私自给顾客增加商品,尽管有时这么做了可以使顾客支付的费用更低。
    比如根据上述的优惠活动,最低的价格购买3束花和2个花瓶的价格是14元:两个花瓶和一束鲜花享受优惠价格10元。另外两束鲜花采用普通价格购买花费4元,总费用14元。

    入力形式

    第一行,一个整数b,表示需要购买b种不同的商品 (0 <= b <= 5)
    接下来b行,每行3个整数c,k和p,c(1 <= c <= 999)表示该种商品的编号,k(1 <= k <= 5)需要购买该商品的数量,p (1 <= p <= 999)表示该商品的价格。
    接下来一行,一个整数s,表示有s(0 <= s <= 99)种优惠活动
    接下来s行,每行描述一种优惠活动的详细情况:第一个整数n(1 <= n <= 5)表示,该活动中商品的种数。接下来有n对数字(c,t),表示编号为c的商品需要购买t(1 <= t <= 5)个才能享受优惠。最后一个数字v(1 <= v <= 9999) ,表示享受该优惠活动需要支付的费用。(v一定小于该优惠活动中所有商品的普通价格总和)

    出力形式

    一个整数,表示最小要支付的费用

    サンプル入力

    2
    7 3 2
    8 2 5
    2
    1 7 3 5
    2 7 1 8 2 10

    サンプル出力

    14


    ソース  IOI 1995