Maximize Year-End Wealth through Sequential Investments

Little Q started the year with \(10^5\) yuan and now wants to maximize his wealth by investing in various financial products. There are \(N\) available investment products. Each product is described by three parameters: the purchase time \(s\) (in days from the start of the year), the investment duration \(d\) (in days), and the annual interest rate \(r\). When investing in a product, the money grows by the factor \(\left(1+\frac{r\cdot d}{365}\right)\). Note that at any moment, Little Q may have at most one investment product active. Only products that finish on or before day 365 can be used.

Your task is to help Little Q determine the maximum amount of money he can have at the end of the year (day 365) if he selects a non‐overlapping sequence of investments optimally.

Hint: You can model this problem as a type of weighted interval scheduling where the weights are multiplicative.

inputFormat

The first line contains an integer \(N\) (the number of investment products). Each of the following \(N\) lines contains three numbers: an integer \(s\) (the purchase time in days, \(0 \leq s \leq 365\)), an integer \(d\) (the investment duration in days), and a floating-point number \(r\) (the annual interest rate). For each product, the finishing time is \(s+d\); only consider products with \(s+d \leq 365\).

outputFormat

Output a single number representing the maximum amount of money that Little Q can have by day 365. Your answer will be considered correct if it is printed with at least 6 digits of precision after the decimal point.

sample

1
0 365 0.1

110000.000000