Optimal Gold Voucher Trading

At a gold voucher exchange, there are two types of vouchers: A and B. On day K the vouchers have values A_K and B_K (in RMB per unit) respectively. In addition, the exchange specifies a ratio parameter \(\mathrm{Rate}_K\) for that day.

The exchange supports two operations:

• Selling vouchers: The customer chooses a percentage \(OP\) (a real number in the interval [0,100]), and sells \(OP\%\) of both the A and B vouchers they hold. At day K the returned money is computed according to the current values of the vouchers.
• Buying vouchers: The customer pays \(IP\) RMB. The exchange then gives the customer vouchers whose total market value is exactly \(IP\) RMB (based on values on that day) and in such quantities that the newly bought vouchers satisfy \[ \frac{x}{y} = \mathrm{Rate}_K, \] where \(x\) and \(y\) are the numbers of A and B vouchers, respectively. In other words, if day K values are \(A_K\) and \(B_K\), the cost to buy \(x\) and \(y\) vouchers is \[ x \cdot A_K + y \cdot B_K = IP, \quad \text{with } x = \mathrm{Rate}_K \cdot y. \] Thus the customer receives \[ y = \frac{IP}{\mathrm{Rate}_K \cdot A_K + B_K} \quad \text{and} \quad x = \frac{\mathrm{Rate}_K \cdot IP}{\mathrm{Rate}_K \cdot A_K + B_K}. \]

The customer knows the future for N days, i.e. for each day \(K=1,2,\dots,N\) the values \(A_K\), \(B_K\) and the ratio \(\mathrm{Rate}_K\) are known. Starting with \(S\) RMB and no vouchers, the customer may perform an arbitrary number of operations — even multiple operations per day. At the end of day \(N\) the customer must end with only RMB. What is the maximum amount of RMB obtainable by a suitable sequence of operations?

Trading mechanics explained:

You may convert money into vouchers or vouchers into money partially. In a buy on day \(i\), spending an amount \(M\) results in vouchers that, if entirely sold on a later day \(j\) (via a \(100\%\) sell operation), yield an amount equal to

[ M \times \frac{\mathrm{Rate}_i\cdot A_j+B_j}{\mathrm{Rate}_i\cdot A_i+B_i}. ]

Your task is to decide the optimal times (and amounts) to convert between money and vouchers so that, after day \(N\), you maximize your RMB holdings.

inputFormat

The first line contains two numbers: an initial amount \(S\) (a real number) and an integer \(N\) (the number of days).

Then \(N\) lines follow. The \(i\)th of these lines contains three real numbers: \(A_i\), \(B_i\), and \(\mathrm{Rate}_i\), representing the unit values of voucher A, voucher B, and the ratio parameter for day \(i\), respectively.

outputFormat

Output a single real number, which is the maximum amount of RMB obtainable after day \(N\). It is recommended to output the answer using 6 digits after the decimal point.

sample

100 3
1 1 1
1 2 2
2 2 3

225.000000