Problem J

Mobilization is a brand new strategy game in which you are required to 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 equal to 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).


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

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


The output is a line containing one number, the greatest possible efficacy expressed with a relative or absolute error less than $0.005$.

Sample Input 1 Sample Output 1
4 100000
300 1 0.02
500 0.2 1
250 0.3 0.1
1000 1 0.1
Sample Input 2 Sample Output 2
2 100
1 0.1 1
1 1 0.1

Please log in to submit a solution to this problem

Log in