哈罗哈的大披萨 【淡蓝】

Description:

热风哈罗哈（三牌楼）店正在搞活动：他们将提供一个大披萨给第一个告诉他们以下信息的人：一次购买任一种披萨，哪种单位面积的价格最低。问题初步想一想，好像是这么解决：“对于每个披萨计算平均价格，那么最小值就是答案了。”

但是，这个问题不是这么简单，因为在热风哈罗哈店里：对某些披萨，是送打折优惠券的，凭这些优惠券可以得到另一个便宜些甚至差点的披萨，这些优惠券可合并使用。披萨必须一个接一个的买，不可能使用优惠券对一个已买的披萨打折。你能第一个解决这个问题，得到大披萨吗？

Input:

输入文件包含几个测试用例。每个测试用例包括：

l       1行：一个数m，为热风哈罗哈提供披萨数目。当m=0时输入终止。一般1 ≤ m ≤ 15。

l       随后的m 行描述每个披萨。每一行描述披萨i (1 ≤ i ≤ m) ，开始3个整数p_i, a_i 和 n_i 表示披萨的价格、面积、和购买它时得到的打折优惠券数目，1 ≤ p_i ≤ 10000, 1 ≤ a_i ≤ 10000 , 0 ≤ n_i < m。

l       随后是n_i 对整数x_i,j 和 y_i,j 表示你得到打折的披萨序号x_i,j (1 ≤ x_i,j ≤ m, x_i,j ≠ i) 以及买披萨x_i,j得到的折扣y_i,j，以百分比表示(1 ≤ y_i,j ≤ 50)。可以假设对于每个i ，x_i,j 两两不同。

Output:

对于每个测试用例:      

打印一行，为通过一次购买任何一种披萨所能得到的单位面积最低价钱. 四舍五入到小数点后4位。

注意到你能组合任意数目的打折优惠券：对于价格为10的披萨和两个折扣为50和20的优惠券，你将只需支付10 * 0.8 * 0.5 = 4单位的钱。

Sample Input:

1
80 30 0
2
200 100 1 2 50
200 100 0
5
100 100 2 3 50 2 50
100 100 1 4 50
100 100 1 2 40
600 600 1 5 10
1000 10 1 1 50
0

Sample Output:

2.6667
1.5000
0.5333

Note:

本题由旧版NOJ导入，来源：“IBM南邮杯”团队赛2009