Preparing NOJ

最少费用购物

1000ms 65536K

Description:

商店中每种商品都有标价。例如,一朵花的价格是2元。一个花瓶的价格是5元。为了吸引顾客,商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组,并降价销售。例如,3朵花的价格不是6元而是5元。2个花瓶加1朵花的优惠价是10元。试设计一个算法,计算出某一顾客所购商品应付的最少费用。

对于给定欲购商品的价格和数量,以及优惠商品价,编程计算所购商品应付的最少费用。

Input:

输入的第1行中有1个整数B0B5),表示所购商品种类数。接下来的B行,每行有3个数CKPC表示商品的编码(每种商品有唯一编码),1C999K表示购买该种商品总数,1K5P是该种商品的正常单价(每件商品的价格),1P999。请注意,一次最多可购买5*525件商品。再输入提供优惠商品价数据,第1行中有1 个整数S0S99),表示共有S 种优惠商品组合。接下来的S 行,每行的第一个数描述优惠商品组合中商品的种类数j。接着是j 个数字对(CK),其中C是商品编码,1C999K表示该种商品在此组合中的数量,1K5。每行最后一个数字P1P9999)表示此商品组合的优惠价。

Output:

输出计算出的所购商品应付的最少费用。

Sample Input:

2
7 3 2
8 2 5

2
1 7 3 5
2 7 1 8 2 10

Sample Output:

14

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1236

Tags

Submitted 7

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet