Ваня играет в компьютерную игру. В ней есть $$$n$$$ квестов. Каждый из квестов можно один раз улучшить, после этого награда за его выполнение увеличится. У каждого квеста есть $$$3$$$ характеристики: $$$a_{i}$$$, $$$b_{i}$$$, $$$p_{i}$$$. Это награда за выполнение квеста до улучшения, награда за выполнение квеста после его улучшения ($$$a_{i} < b_{i}$$$) и вероятность успешно выполнить этот квест.
Каждую секунду Ваня может попытаться выполнить любой квест, и выполнит его с вероятностью $$$p_{i}$$$. В этом случае Ваня получит вознаграждение за него и возможность улучшить один любой квест (не обязательно тот, который он выполнил), в противном случае он не получит ничего. После выполнения квесты не исчезают.
У Вани в распоряжении есть $$$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}$$$.
3 2
3 1000 0.5
1 2 0.48
3 20 0.3
252.2500000000000
2 2
1 1000 0.1
2 3 0.2
20.7200000000000
Название |
---|