OpenJudge

4:HSYOI 小店购物

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
128000kB
描述

  Grant是一个个体户老板,他经营的小店因为其丰富的优惠方案深受附近居民的青睐,生意红火。小店的优惠方案十分简单有趣。Grant规定:在一次消费过程中,如果您在本店购买了精制油的话,您购买香皂时就可以享受2.00/块的优惠价;如果您在本店购买了香皂的话,您购买可乐时就可以享受1.50/听的优惠价……诸如此类的优惠方案就是说:如果您在本店购买了商品A的话,您就可以以P/件的优惠价格购买商品B(购买的数量不限)。有趣的是,你需要购买同样一些商品,由于不同的购买顺序,Grant老板可能会叫你付不同数量的钱。比如你需要一块香皂(原价2.50元)、一瓶精制油(原价10.00元)、一听可乐(原价1.80),如果你按照可乐,精制油,香皂这样的顺序购买的话,Grant老板会问你要13.80元;而如果你按照精制油,香皂,可乐这样的顺序购买的话,您只需付13.50元。

现在该村的居民请你编写一个程序,告诉你Grant小店商品的原价,所有优惠方案及所需的商品,计算至少需要花多少钱。不允许购买任何不需要的商品,即使这样做可能使花的钱更少。


输入
第一行为一个整数n(1<=n<=50),表示Grant小店的商品种数。接下来是n行,其中第(i+1)行由一个实数Ci (0 < Ci<=1000)和一个整数Mi (0<=Mi<=100)组成,其间由一个空格分隔,分别表示第i种商品的原价和所需数量。第(n+2)行又是一个整数k,表示Grant小店的优惠方案总数。接着k行,每行有二个整数A,B(1<=A,B<=n)和一个实数P( 0<=P < 1000),表示一种优惠方案,即如果您购买了商品A,您就可以以P元/件的优惠价格购买商品B。所有优惠方案的(A,B)都是不同的。为了方便,Grant不收分币,所以所有价格都不会出现分。
输出
输出一行,只有一个实数,表示最少需要花多少钱。输出实数须保留两位小数。
样例输入
4
10.00 1
1.80 1
3.00 0
2.50 2
2
1 4 2.00
4 2 1.50
样例输出
15.50
全局题号
10892
添加于
2016-07-08
提交次数
2
尝试人数
2
通过人数
0