Welcome to ZOJ
83 - ZOJ Monthly, September 2009 - I
Wistone and Owenwater

Time Limit: 1 Second      Memory Limit: 32768 KB

DD and his girlfriend love travelling, one day they go to a strange cave. DD suddenly found some valuable stones and water named "wistone" and "owenwater". If DD could take them to the outer world, he could earn a lot:) Unfortunately, DD only takes a bottle with capacity W with him. He can only use this bottle to take them back.

As you know, each type of "wistone" and "owenwater" has different value, and "wistone" cannot be divided into smaller ones while "owenwater" can be taken as much as you want if it is avaliable.

Now, you are asked to calculate the maximum value DD can take back.


This problem contains several test cases, you should process it to the end of input.

For each test case, there are two integers in the first line, N (1 <= N <= 100) and W ( 0 <= W <= 50000), N indicates the total type number of "wistone" and "owenwater". W indicates the capacity of bottle.

Then next n lines, each line contains three integers, ai, bi (1 <= ai, bi <= 1000) and ti. ai indicates the amount, bi indicates the total value and if ti is 0, it means this one is "wistone" otherwise it is "owenwater".


For each test case, you should only output one number(accurate to 2 digits to the right of the decimal point), namely the maximum value DD can get.

Sample Input

3 150
100 100 0
100 100 0
130 10 1

Sample Output


Author: WANG, Naiyan
Source: ZOJ Monthly, September 2009
Submit    Status