题目描述

小 A 正在玩游戏。

这个游戏一共有 $n$ 个关卡。对于第 $i$ 个关卡，小 A 需要花费 $c_i$ 的时间来挑战，他有 $p_i$ 的概率挑战成功。与此同时，一些关卡可能会有一个前置关卡 $d_i$，他必须要完成关卡 $d_i$ 以后才能挑战关卡 $i$。

如果某个关卡挑战失败了，所有关卡都需要重新挑战。

由于小 A 想要赶紧去卷，他想要尽快完成所有挑战。请你求出他完成所有关卡的最小期望时间。

保证一定存在方案能在有限期望时间内完成所有关卡。

输入格式

第一行一个非负整数 $n$，表示关卡个数。

接下来 $n$ 行，每行三个数：

c_i p_i d_i

输出格式

输出一行一个数，表示小 A 的最小挑战时间。

由于精度问题，你只需要输出：

你的答案与标准答案的绝对或相对误差需要小于 $10^{-6}$。

样例 1 输入

4
100 0.5 0
200 0.1 1
10 0.5 2
10 0.9 0

样例 1 输出

190.45

样例 2 输入

见 level2.in。

样例 2 输出

见 level2.out。

测试点约束

对于所有数据：

且 $p_i$ 精确到小数点后六位。