V8发现，在实验室楼下，小苹果因为其丰富的经营优惠方案深受同学的青睐，生意十分红火。因其经营优惠方案十分简单有趣：

一次消费过程中，如您在本店购买了绿茶，购买香肠时就可以享受 2.00 元/根的优惠价； 如果您在本店购买了香肠，您购买可乐就可以享受 1.50 元/听的优惠价；……，诸如此类的优惠方案就是说：如您在本店购买了商品 A，您就可以以 P 元/件的优惠价购买商品 B（购买的数量不限）。 有趣的是，你需要购买同样一些商品，由于不同的购买顺序，老板可能会叫你付不同数量的钱。比如，您需要一根香肠（原价 2.50 元/根）、一瓶绿茶（原价 10.00 元/瓶）、一听可乐（原价 1.80 元/听），如果你按照可乐、绿茶、香肠这样的顺序购买，老板会问你要 13.80 元；而如果你按照绿茶、香肠、可乐这样的顺序购买，你只需付 13.50 元。 V8于是请大家编写一个程序：在告诉商品的原价，所有的优惠方案及所需的商品后，计算至少需要花费多少钱（不允许购买任何不需要的商品，即使这样做可能使花费的钱更少）。 1.可能有自己优惠自己的，即第二个开始就可以优惠了 2.而且可以先只买某种物品的一个，再通过其他的优惠使得该类物品剩下的享受优惠.

输入第一行为一个整数 n（1<=n<=50），表示小店的商品种数。

接下来是 n 行，其中第（i+1）行由一个实数 Ci（0

然后是一个整数K(1<=K<=500)

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

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