ml2 | Big Stonks

Since he learned Rust, Dario is now able to write software that would have never been possible with inferior languages such as C/C++. For example, he recently wrote a software that can predict with perfect accuracy the stock market prices for the next N days. Knowing these prices, he is now looking for a strategy that will make him rich.

Dario selected $K$ individual stocks, and for each of them he computed the buying price $B$ and selling price $S$ for each of the $N$ consecutive days. For example, let’s say that Dario’s list contains $K = 3$ stocks ([A]pple, [F]acebook, [G]oogle) and that he computed their prices for $N = 2$ consecutive days:

The prices in the list are expressed in Euro, and are always integers. The total starting budget that Dario can invest is $1$ Euro. For the purpose of this problem, we assume that it’s possible to buy any fraction of a stock (e.g. you could buy $\frac{1}{5}$ of an Apple stock on the first day for $1$ Euro). Help Dario find the maximum profit that he can make by optimally investing $1$ Euro over those $N$ days.

Input data

The first line contains two integers $N$ and $K$.

$N$ lines follow: the $i$-th line contains $K$ pairs of integers: the buying price $B_{i,j}$ and selling price $S_{i,j}$ for the $j$-th stock on the $i$-th day.

Output data

You need to write a single line with a number: the maximum possible amount of Euro that Dario can have at the end of the $N$ days. The answer will be considered correct if the absolute or relative error is lower than $10^{−6}$.

Constraints and clarifications

• $1 \leq N, K \leq 3 \ 000$;
• $1 \leq S_{i,j} \leq B_{i,j} \leq 100$;
• It is guaranteed that the answer will fit in a $64$ bit floating point variable (double).

Example 1

stdin

2 3
5 3 6 2 5 4
8 6 7 6 6 5

stdout

1.2

Explanation

In the first sample case, Dario can buy $\frac{1}{5}$ of the first stock on the first day (when it costs $5$ Euro) and sell it on the second day (when it sells for $6$ Euro), scoring $\frac{1}{5} \cdot 6$ = $1.20$ Euro.

Example 2

stdin

3 3
5 3 6 2 5 4
8 6 7 6 6 5
14 13 15 14 11 9

stdout

2.6

Explanation

In the second sample case note that first two days are unchanged. One almost-optimal strategy in this case would be to reinvest the $1.20$ Euro of the second day by buying $\frac{1.2}{7}$ = $0.1714285714$ units of the second stock, which can be sold on the last day for $\frac{1.2}{7} \cdot 14$ = $2.40$ Euro. However, there is an even better solution: keep the $\frac{1}{5}$ units of the first stock bought on the first day, and sell it on the third day for $\frac{1}{5} \cdot 13$ = $2.60$ Euro!