Background

Special for beginners, ^_^

Description

Grant是一个个体户老板，他经营的小店因为其丰富的优惠方案深受附近居民的青睐，生意红火。小店的优惠方案十分简单有趣。Grant规定：在一次消费过程中，如果您在本店购买了精制油的话，您购买香皂时就可以享受2.00元/块的优惠价；如果您在本店购买了香皂的话，您购买可乐时就可以享受1.50元/听的优惠价……诸如此类的优惠方案就是说：如果您在本店购买了商品A的话，您就可以以P元/件的优惠价格购买商品B（购买的数量不限）。有趣的是，你需要购买同样一些商品，由于不同的购买顺序，Grant老板可能会叫你付不同数量的钱。比如你需要一块香皂（原价2.50元）、一瓶精制油（原价10.00元）、一听可乐(原价1.80元)，如果你按照可乐，精制油，香皂这样的顺序购买的话，Grant老板会问你要13.80元；而如果你按照精制油，香皂，可乐这样的顺序购买的话，您只需付13.50元。 现在该村的居民请你编写一个程序，告诉你Grant小店商品的原价，所有优惠方案及所需的商品，计算至少需要花多少钱。不允许购买任何不需要的商品，即使这样做可能使花得钱更少。

Format

Input

，第一行为一个整数n（1<=n<=50），表示Grant小店的商品种数。接下来是n行，其中第(i+1)行由一个实数C ~i ~ (0<C ~i~ <=1000)和一个整数M ~i ~ (0<=M ~i~ <=100)组成，其间由一个空格分隔，分别表示第i种商品的原价和所需数量。第(n+2)行又是一个整数k，表示Grant小店的优惠方案总数。接着k行，每行有二个整数A，B（1<=A,B<=n）和一个实数P（ 0<=P<1000），表示一种优惠方案，即如果您购买了商品A，您就可以以P元/件的优惠价格购买商品B，P小于商品B的原价。所有优惠方案的（A,B）都是不同的。为了方便，Grant不收分币，所以所有价格都不会出现分。

Output

只有一个实数，表示最少需要花多少钱。输出实数须保留两位小数。

Samples

4
10.00 1
1.80 1
3.00 0
2.50 2
2
1 4 2.00
4 2 1.50

15.50

Limitation

1s, 1024KiB for each test case.