题目背景

JSOI集训队的队员发现，在他们经常活动的集训地，有一个小店因为其丰富的经营优惠方案深受附近居民的青睐，生意红火。

题目描述

小店的优惠方案十分简单有趣：

一次消费过程中，如您在本店购买了精制油的话，您购买香皂时就可以享受 $2.00$ 元 / 块的优惠价；如果您在本店购买了香皂的话，您购买可乐时就可以享受 $1.50$ 元 / 听的优惠价……诸如此类的优惠方案可概括为：如果您在本店购买了商品 $A$ 的话，您就可以以 $P$ 元 / 件的优惠价格购买商品 $B$（购买的数量不限）。

有趣的是，你需要购买同样一些商品，由于不同的买卖顺序，老板可能会叫你付不同数量的钱。比如你需要一块香皂（原价 $2.50$ 元）、一瓶精制油（原价 $10.00$ 元）、一听可乐（原价 $1.80$ 元），如果你按照可乐、精制油、香皂这样的顺序购买的话，老板会问你要 $13.80$ 元；而如果你按照精制油、香皂、可乐这样的顺序购买的话，您只需付 $13.50$ 元。

该处居民发现 JSOI 集训队的队员均擅长电脑程序设计，于是他们请集训队的队员编写一个程序：在告诉你该小店商品的原价，所有优惠方案及所需的商品后，计算至少需要花多少钱（不允许购买任何不必要的商品，即使这样做可能使花的钱更少）。

输入格式

输入文件第一行为一个整数 $n\ (1 \le n \le 50)$，表示小店的商品总数。

接下来是 $n$ 行，其中第 $i+1$ 行由一个实数 $c_i\ (0<c_i \le 1000)$ 和一个整数 $m_i\ (0 \le m_i \le 100)$ 组成，其间由一个空格分隔，分别表示第 $i$ 种商品的原价和所需数量。第 $n+2$ 行又是一个整数 $k\ (1 \le k \le 500)$，表示小店的优惠方案总数。

接着 $k$ 行，每行有二个整数 $A,B(1 \le A,B \le n)$ 和一个实数 $P(0 \le P<1000)$，表示一种优惠方案，即如果您购买了商品 $A$，您就可以以 $P$ 元 / 件的优惠价格购买商品 $B$，$P$ 小于商品 $B$ 的原价。所有优惠方案的 $(A,B)$ 都是不同的。为了方便老板不收分币，所以所有价格都不出现单位分。

输出格式

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

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

15.50

提示

数据范围见输入格式