### National Olympiad in Informatics, China, 2007

## Day 1, Problem 2 - Cash Exchange

Little Y has recently been working at a currency exchange center. The currency exchange center only offers two types of vouchers to be exchanged: commemorative voucher A (henceforth known as voucher A) and commemorative voucher B (henceforth known as voucher B). All voucher-holding customers possess their very own account. The quantity of vouchers a customer has may be a real number.

Rising and falling daily with the waves of the market, the two types of vouchers each has their own values at any given time, and each unit of a voucher can be traded that day for some amount of cash. We note that on day `K`, the values of voucher A and voucher B are respectively `A _{K}` and

`B`(dollars/unit voucher).

_{K}To make it more convenient for customers, the exchange center offers a very easy system to make transactions: the ratio exchange method. There are two different aspects to the ratio exchange method:

- Selling vouchers: the customer provides a real number
`OP`in the range [0, 100] as the selling ratio. This means that`OP`% of voucher A and`OP`% of voucher B are exchanged for cash with the rate at that point in time. - Buying vouchers: the customer pays
`IP`dollars, and the exchange center takes this money to exchange it for vouchers. Furthermore, the ratio between the value of voucher A and voucher B on day`K`just happens to be`Rate`._{K}

For example, let's assume for the next 3 three days the following changes in the values of `A _{K}`,

`B`, and

_{K}`Rate`:

_{K}Time | A_{K} | B_{K} | Rate_{K} |
---|---|---|---|

Day 1 | 1 | 1 | 1 |

Day 2 | 1 | 2 | 2 |

Day 3 | 2 | 2 | 3 |

Let's say that on one day, a customer has 100 dollars but no vouchers of any kind. The customer carry out the following transactions:

Time | Transaction | Cash (Dollars) | Voucher A | Voucher B |
---|---|---|---|---|

Initial | None | 100 | 0 | 0 |

Day 1 | Buy – 100 dollars | 0 | 50 | 50 |

Day 2 | Sell – 50% | 75 | 25 | 25 |

Day 2 | Buy – 60 dollars | 15 | 55 | 40 |

Day 3 | Sell – 100% | 205 | 0 | 0 |

Note that there may be multiple transactions on a single day.

Little Y is a very economically-minded worker. After a relatively long time conducting operations and market estimates, he already knows within the future `N` days what the values of vouchers A and B, as well as rate will be. He wishes to calculate, if one starts with `S` dollars, what is the maximum amount of cash (in dollars) that can be obtained after `N` days.

### Input Format

The first line contains two positive integers `N` and `S`, representing the number of days that little Y's can foresee and the starting amount of cash respectively.

Within the next `N` lines, the `K`-th line contains three real numbers `A _{K}`,

`B`, and

_{K}`Rate`.

_{K}### Output Format

Output a single real number `MaxProfit`, indicating the maximum amount of cash in dollars that can be obtained after all operations on the `N`-th day has finished, accurate to 3 decimal places. Your answer will be considered correct if its absolute difference with the correct answer is no larger than 0.001.

### Sample Input

3 100 1 1 1 1 2 2 2 2 3

### Sample Output

225.000

### Explanation

Time | Transaction | Cash (Dollars) | Voucher A | Voucher B |
---|---|---|---|---|

Initial | None | 100 | 0 | 0 |

Day 1 | Buy – 100 dollars | 0 | 50 | 50 |

Day 2 | Sell – 100% | 150 | 0 | 0 |

Day 2 | Buy – 150 dollars | 0 | 75 | 37.5 |

Day 3 | Sell – 100% | 225 | 0 | 0 |

### Constraints

The test data ensures that the precision needed for calculations will not exceed 10^{−7}.

For 40% of the test cases, `N` ≤ 10;

For 60% of the test cases, `N` ≤ 1 000;

For 100% of the test cases, `N` ≤ 100 000;

For 100% of the test cases:

- 0 <
`A`≤ 10;_{K} - 0 <
`B`≤ 10;_{K} - 0 <
`Rate`≤ 100;_{K} `MaxProfit`≤ 10^{9}.

### Hints

The input may be very large, please use faster methods of input.

There must be an optimal series of transaction satisfying the conditions:

- each buying transaction uses up all of the cash, and
- each selling transaction sells all of the vouchers.

All Submissions

Best Solutions

**Point Value:** 30 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 256M

**Added:** Jul 25, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

JeffreyLon May 28, 2016 - 10:17:40 pm UTC Problem with judge?jargonon May 29, 2016 - 3:32:44 pm UTC Re: Problem with judge?Edit: Rejudging is complete. The only users that was affected was kobortor. I only rejudged submissions that had an impact on a user's points, so I did not re-run your test submission.

Thanks for your report.

kobortoron May 29, 2016 - 10:16:17 pm UTC Re: Problem with judge?