278. Fuel

Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

A fuel station has infinite amount of each of N kinds of fuel. Each kind of fuel has density ai, cost bi and intensity ci. m kilograms of such fuel has volume mai, intensity mci and costs mbi dollars. Your car can store any mixture of different kinds of fuel such that the overall volume does not exceed A. You have B dollars. Your task is to determine the maximal overall intensity of the fuel you can buy. Note that you can buy any nonnegative amount of any kind of fuel, not necessarily an integer number of kilograms.

The first line of the input contains three integers N, A, B (1≤ N≤ 75000, 1≤ A,B≤ 1000). Each of the next N lines describes one kind of fuel. i+1-st line contains three integers ai, bi, ci (0i,bi,ci≤ 100).

The only line of the output must contain single number with at least 6 digits after the decimal point, being the maximal overall intensity.

sample input
sample output
2 1 1 
1 2 6
2 1 6

Novosibirsk SU Contest #2, by Novosibirsk Team #1

Online Contester Team © 2002 - 2010. All rights reserved.