Little Y recently started working at a gold voucher exchange. The exchange only issues two types of gold vouchers: Type A commemorative vouchers (hereinafter referred to as "Type A vouchers") and Type B commemorative vouchers (hereinafter referred to as "Type B vouchers"). Every customer holding gold vouchers has their own account. The number of gold vouchers can be a real number.
Every day, as the market fluctuates, both types of gold vouchers have a current value, which is the amount of RMB that one unit of a gold voucher can be exchanged for on that day. We record the values of Type A and Type B vouchers on day $K$ as $A_K$ and $B_K$ (RMB/unit of gold voucher), respectively.
To facilitate customers, the gold voucher exchange provides a very convenient trading method: the proportional trading method. The proportional trading method consists of two aspects:
a) Selling gold vouchers: The customer provides a real number $OP$ in the range $[0, 100]$ as the selling proportion, which means: $OP\%$ of the Type A vouchers and $OP\%$ of the Type B vouchers are exchanged for RMB at their current values.
b) Buying gold vouchers: The customer pays $IP$ RMB, and the exchange will provide the user with gold vouchers having a total value of $IP$, such that the ratio of Type A vouchers to Type B vouchers provided to the customer on day $K$ is exactly $Rate_K$.
For example, suppose the changes in $A_K$, $B_K$, and $Rate_K$ over the next 3 days are as follows:
| Time | $A_K$ | $B_K$ | $Rate_K$ |
|---|---|---|---|
| Day 1 | 1 | 1 | 1 |
| Day 2 | 1 | 2 | 2 |
| Day 3 | 2 | 2 | 3 |
Assume that on the first day, the user has 100 RMB but no gold vouchers. The user can perform the following operations:
| Time | User Operation | RMB | Type A Vouchers | Type B Vouchers |
|---|---|---|---|---|
| Account Opening | None | 100 | 0 | 0 |
| Day 1 | Buy 100 RMB | 0 | 50 | 50 |
| Day 2 | Sell 50% | 75 | 25 | 25 |
| Day 2 | Buy 60 RMB | 15 | 55 | 40 |
| Day 3 | Sell 100% | 205 | 0 | 0 |
Note that multiple operations can be performed on the same day.
Little Y is a very economically minded employee. Through long-term operation and market analysis, he already knows the values of Type A and Type B vouchers and the $Rate$ for the next $N$ days. He wants to calculate the maximum amount of money he can obtain after $N$ days if he starts with $S$ RMB.
Input
The first line contains two positive integers $N$ and $S$, representing the number of days Little Y can foresee and the initial amount of money, respectively.
The next $N$ lines each contain three real numbers $A_K$, $B_K$, and $Rate_K$, with meanings as described in the problem.
Output
A single real number $MaxProfit$, representing the maximum amount of money that can be obtained at the end of the operations on day $N$. The answer should be rounded to 3 decimal places.
Examples
Input 1
3 100 1 1 1 1 2 2 2 2 3
Output 1
225.000
Note
| Time | User Operation | RMB | Type A Vouchers | Type B Vouchers |
|---|---|---|---|---|
| Account Opening | None | 100 | 0 | 0 |
| Day 1 | Buy 100 RMB | 0 | 50 | 50 |
| Day 2 | Sell 100% | 150 | 0 | 0 |
| Day 2 | Buy 150 RMB | 0 | 75 | 37.5 |
| Day 3 | Sell 100% | 225 | 0 | 0 |
Subtasks
This problem has no partial points. Your program's output must be within 0.001 of the standard answer to receive full marks for the test case; otherwise, it receives no points.
Constraints
The test data is designed such that the precision error will not exceed $10^{-7}$.
- For 40% of the test data, $N \le 10$.
- For 60% of the test data, $N \le 1\,000$.
- For 100% of the test data, $N \le 100\,000$.
- For 100% of the test data:
- $0 < A_K \le 10$
- $0 < B_K \le 10$
- $0 < Rate_K \le 100$
- $MaxProfit \le 10^9$
Note
The input file may be very large; please use fast I/O methods. There must exist an optimal buying and selling strategy that satisfies: Every buy operation uses all available RMB. Every sell operation sells all held gold vouchers.