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