【问题描述】

小 A 要对 B 国的 n 个城市发起进攻。

城市从 1 ~ n 进行编号。进攻每个城市需要付出一定的代价。并且要想占领一个城市，可能需要对该城市进行多次进攻。对于城市 i，进攻一次需要付出的代价为 $S_i$，占领该城市需要进攻 $T_i$ 次。

根据当前获取的情报，得知有些城市会向别的城市派遣援兵。假如城市 u 会向城市 v 派遣援兵，那么当城市 u 被进攻过一次后，它将不得不停止向城市 v 派遣援兵，则进攻城市 v 的代价将会降低。

小 A 正在寻求一种进攻方案，使得占领所有城市需要付出的总代价最小。你能帮助他吗？

【输入格式】

第一行：包含一个整数 n；

接下来 n 行，每行包含两个数：实数 $S_i$, 整数 $T_i$，含义如题所述；

接下来一行，包含一个整数 k，表示有 k 个情报；

接下来 k 行，每行表示一个情报信息，包含三个数：整数 u，整数 v，实数 w，表示如果已经进攻过城市 u，则进攻城市 v 的代价将降低为 w。数据保证 $w < S_v$。

【输出格式】

输出只有一行，表示占领所有城市需要付出的最小总代价，结果保留 2 位小数。

【输入样例1】

3
1.00 1
2.34 2
3.50 4
2
3 2 2.00
1 3 1.50

【输出样例1】

11.00

【输入样例2】

3
10.00 1
2.34 2
3.50 4
3
1 2 1.50
2 3 2.00
3 1 0.50

【输出样例2】

12.34

【数据范围】

100% 的数据：N ≤ 50; 0 < $S_i$ ≤ 1000; 0 < $T_i$ < 100, 0 ≤ k ≤ 500。

其中有 10% 的数据：k ≤ 1;

另有 10% 的数据：N ≤ 10;

另有 10% 的数据：派遣援兵的关系形成一条链；

另有 10% 的数据：派遣援兵的关系形成一个环；

另有 10% 的数据：派遣援兵的关系形成一棵树。