EXCHANGE - Exchange

There are 3 kinds of money in a planet far away from the earth: Mone, Luck, and Rpin. There's a money exchange company in this planet. You must go to this company if you want to do some money exchange, and, more autocratically, this company regulate the exchange rate of each pair of these 3 kinds of money.

The money exchange will be done in the following two ways:

(A)

You give the company a real number x in the range (0,100], the company will exchange x% of your Mone and x% of your Luck to equal Rpin according to the exchange rate of that day.

(B)

You give the company a real number x, the company will exchange your x Rpin to some Mone and Luck, whose value is equal to x Rpin according to the exchange rate of that day, and, the value of Mone is Rate times of the value of Luck.

You can do many exchange operations in the same day.

Now, as the excellant spy in this planet, you know the exchange rate between Mone and Rpin of each of the next n days(ai Rpin per Mone), and the exchange rate between Luck and Rpin of each of the next n days(bi Rpin per Luck), and, each Rate of the next n days( Ratei). you have S Rpin in the start, and you want to get most Rpin in the nth day later.

Input

Multiple test cases, the number of them( <=5 ) is given in the very first line.

For each test case:

The first line contains a integer number n(1<=n<=100000) and a real number S.n lines follow, each contains 3 real numbers: ai(between 0 and 10), bi(between 0 and 10), Ratei(between 0 and 100).

Output

For each test case, output one line contains a real number with 3 digits after decimal point, which denotes to the answer. You can assume it is less than 1000000000.

Example

Input:
1
3 100
1 1 1
1 2 2
2 2 3

Output:
225.000

Note

For the example, one optimal way to gain 225 Rpin is as follows:

Day 1: Exchange all Rpin to Mone and Luck (1:1). Gain 50 Mone and 50 Luck.

Day 2: Exchange all Mone and Luck to Rpin. Gain 50x1 + 50x2 = 150 Rpin. Then exchange all Rpin to Mone and Luck(2 : 1). Gain 75 Mone and 37.5 Luck.

Day 3: Exchange all Mone and Luck to Rpin. Gain 75x2 + 37.5x2 = 225 Rpin.

Warning: large input/output data, be careful with certain languages; the time limit is somewhat strict for this problem

Added by:Fudan University Problem Setters
Date:2007-08-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 2007,Day 1; Translated by Blue Mary

hide comments
2010-08-10 14:00:03 :D
I need help with this problem description. The only way I managed to get correct result for the example is by doing the following:
1. Reverting rates (Mone per ai Rpin, Luck per bi Rpin)
2. Changing the Rate from values proportion to count proportion (the number of Mone is Rate times of the number of Luck)

As I understand it, if I take the problem description literally, the values of Mone and Rpin in example are only getting lower (in respect to Rpin). Because of that you can only loose on exchanging to Rpin, so I really don't see any alternative for point 1.

Could someone explain the example?

Last edit: 2010-08-10 15:31:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.