商店中每种商品都标有价格。例如,一朵花的价格是2元,一个花瓶的价格是5元。为了吸引顾客,商店提供了一组优惠商品价格。优惠商品是把一种或多种商品分成一组,并降价销售。例如3朵花的价格不是6元而是5元,2个花瓶加一朵花的优惠价格是10元。试设计一个算法,计算出某一顾客所购商品应付的最少费用。数据输入:由文件input.txt提供要购商品数据。文件的第一行中有一个证书B(0 <=B <=5),表示要购买商品种数。在接下来的B行中,每行有3个数C,K和P。C表示商品的编号(每种商品有唯一的编码),1 <=C <=999;K表示购买该商品的总数,1 <=K <=5;P表示该种商品的正常单价(每件商品的价格),1 <=P <=999。请注意一次最多可购买5*5=25件商品。
由文件offer.txt提供优惠商品价格数据。文件的第1行中有1个整数S(0 <=S <=99),表示共有S种优惠商品组合。接下来的S行,每行的第一个数描述优惠商品组合中商品的种类数J。接着的是J个数字对(C,K),其中C是商品编号,1 <=C <=999;K表示该商品在此组合中的数量,1 <=K <=5。每行最后一个数字P(1 <=P <=9999)表示此商品组合的优惠价格。结果输出:将计算出的所购商品应付的最少费用输出到文件output.txt。