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(a_i Rpin per Mone), and the exchange rate between Luck and Rpin of each of the next n days(b_i Rpin per Luck), and, each Rate of the next n days( Rate_i). 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: a_i(between 0 and 10), b_i(between 0 and 10), Rate_i(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.