## NOI '07 P2 - Cash Exchange

View as PDF

Points: 30 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type
##### National Olympiad in Informatics, China, 2007

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 , the values of voucher A and voucher B are respectively and (dollars/unit voucher).

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:

1. Selling vouchers: the customer provides a real number in the range as the selling ratio. This means that of voucher A and of voucher B are exchanged for cash with the rate at that point in time.
2. Buying vouchers: the customer pays 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 just happens to be .

For example, let's assume for the next 3 three days the following changes in the values of , , and :

Time
Day 1
Day 2
Day 3

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

Time Transaction Cash (Dollars) Voucher A Voucher B
Initial None
Day 2 Sell —
Day 3 Sell —

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 days what the values of vouchers A and B, as well as the rate, will be. He wishes to calculate, if one starts with dollars, what is the maximum amount of cash (in dollars) that can be obtained after days.

#### Input Specification

The first line contains two positive integers and , representing the number of days that little Y's can foresee and the starting amount of cash respectively.
Within the next lines, the -th line contains three real numbers , , and .

#### Output Specification

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

#### 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
Day 2 Sell —
Day 3 Sell —

#### Constraints

The test data ensures that the precision needed for calculations will not exceed .
For of the test cases, ;
For of the test cases, ;
For of the test cases, ;
For of the test cases:

• ;
• ;
• ;
• .

#### 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.

Problem translated to English by Alex.