computergame

Computer Game

Ivan plays some computer game. There are \(n\) quests in the game. Each quest can be upgraded once, this increases the reward for its completion. Each quest has 3 parameters \(a_i\), \(b_i\), \(p_i\): reward for completing quest before upgrade, reward for completing quest after upgrade \((a_i < b_i)\) and probability of successfully completing the quest.

Each second Ivan can try to complete one quest and he will succeed with probability \(p_i\). In case of success Ivan will get the reward and opportunity to upgrade any one quest (not necessary the one he just completed). In case of failure he gets nothing. Quests do not vanish after completing.

Ivan has \(t\) seconds. He wants to maximize expected value of his total gain after \(t\) seconds. Help him to calculate this value.

Input format

First line contains \(2\) integers \(n\) \((1 \leq n \leq 10^5)\) and \(t\) \((1 \leq t \leq 10^{10})\) — number of quests and total time.

Following \(n\) lines contain description of quests. Each description is \(3\) numbers \(a_i\) \(b_i\) \(p_i\) \((1 \leq a_i < b_i ≤ 10^8, 0 < p_i < 1)\) — reward for completing quest before upgrade, reward for completing quest after upgrade and probability of successfully completing the quest. \(a_i\) and \(b_i\) are integers. All probabilities are given with at most \(9\) decimal places.

Output format

Print the expected value.

Your answer will be accepted if absolute or relative error does not exceed \(10^{−6}\). Formally, let your answer be \(a\), and the jury's answer be \(b\). Your answer is considered correct if \(\displaystyle \frac{|a−b|}{\max(b, 1)} \leq 10^{−6}\).

Limits

Subtask # Score Constraints
1 12 \(n, t \leq 2000\)
2 16 \(n \leq 10\)
3 31 \(t \leq 10^5\)
4 41 No additional constraints

Samples

Sample Input 1 Sample Output 1
3 2
3 1000 0.5
1 2 0.48
3 20 0.3
252.2500000000000

Sample Input 2 Sample Output 2
2 2
1 1000 0.1
2 3 0.2
20.7200000000000




Submitting to 'computergame'


You're not logged in! Click here to login


Submitting to 'computergame'


You're not logged in! Click here to login


Submitting .cpp to 'computergame'


You're not logged in! Click here to login

Time Limit: 3 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Codeforces 1067D

Subtask Score
1 12
2 16
3 31
4 41
5 0