Ivan 玩一些电脑游戏。游戏中有 $$$n$$$ 任务。每个任务可以升级一次,这会增加完成奖励。每个任务有$$$3$$$参数$$$a_{i}$$$、$$$b_{i}$$$、$$$p_{i}$$$:升级前完成任务的奖励、升级后完成任务的奖励($$$a_{i} < b_{i}$$$)以及成功完成任务的概率。
每一秒 Ivan 都可以尝试完成一个任务,他将以 $$$p_{i}$$$ 的概率成功。如果成功,伊万将获得奖励和升级任何一项任务的机会(不一定是他刚刚完成的任务)。万一失败,他什么也得不到。任务完成后不会消失。
Ivan 有 $$$t$$$ 秒。他希望在 $$$t$$$ 秒后最大化他的总收益的预期值。帮他算一下这个值。
输入
第一行包含 $$$2$$$ 整数 $$$n$$$ ($$$ 1 \le n \le 10^{5}$$$) 和 $$$t$$$ ($$$ 1 \le t \le 10^{10}$$$) - 任务数量和总时间。
以下 $$$n$$$ 行包含任务描述。每个描述都是 $$$3$$$ 数字 $$$a_{i}$$$ $$$b_{i}$$$ $$$p_{i}$$$ ($$$1 \le a_{i} < b_{i} \le 10^{8}$$$, $$$0 < p_{i} < 1$$$) — 升级前完成任务的奖励、升级后完成任务的奖励以及成功完成任务的概率追求。 $$$a_{i}$$$ 和 $$$b_{i}$$$ 是整数。所有概率最多保留 $$$9$$$ 小数位。
输出
打印期望值。
如果绝对或相对误差不超过 $$$10^{-6}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a-b|}{max(b, \,\, 1)} \le 10^{-6}$$$,则认为您的答案是正确的。
示例
输入 #1
3 2 3 1000 0.5 1 2 0.48 3 20 0.3
输出 #1
252.2500000000000
输入 #2
2 2 1 1000 0.1 2 3 0.2
输出 #2
20.7200000000000