Mobilization

Interview

Time limit2sMemory limit512 MB

Summary

Buy fractional troops within a budget to maximize total health times total potency.

Level: Medium7 of 10
Topics: Greedy, Math, Sorting, Binary search
Solved: No attempts yet

Problem

Mobilization is a brand new strategy game in which you mobilize an army. The army can consist of different types of troops, each of which has a cost, health, and potency. You can acquire any combination of the troop types, even fractional, such that the total cost is no more than the amount you have to spend. The efficacy of the army is its total health value multiplied by its total potency. What is the greatest efficacy you can achieve with the given purchasing constraints?

You may assume that there are always sufficient troops available to buy as many as you want (subject to the total constraint).

Input

The first line contains two integers, the number of different types of troops n (1 ≤ n ≤ 30 000) and the total budget you have to spend b (1 ≤ b ≤ 100 000).

Following this are n lines, each with three values for this troop type: an integer value of its unit cost c (1 ≤ c ≤ 100 000), a real value of its unit health h (0 ≤ h ≤ 1), and a real value of its unit potency p (0 ≤ p ≤ 1). The real values may contain up to 20 digits after the decimal point.

Output

Output one line containing the greatest possible efficacy. A relative or absolute error less than 0.005 is accepted.

Examples2

Example 1

Input

4 100000
300 1 0.02
500 0.2 1
250 0.3 0.1
1000 1 0.1

Expected output

19436.05

Example 2
Input
```
2 100
1 0.1 1
1 1 0.1
```
Expected output
```
3025.00
```