Throughput P87774

Elon Musk is optimizing an assembly line in one of his factories and he needs your help to find an assignment of humanoid robots to stations that maximizes throughput (number of work units processed per hour).

0.60 There are a total of $r$ identical humanoid robots to be distributed among $n$ workstations (numbered 1 to $n$) of the assembly line. At each station $i$, robots collect work units from the output storage of station $i-1$, perform some station-specific operation (such as welding, painting...), and then place the processed work units on the output storage of station $i$, to be collected by robots from station $i+1$. Each robot at station $i$ can process $p_i$ work units per hour. Assume that robots at station 1 collect work units from a warehouse with unlimited supply, and that the output of station $n$ can be consumed at an arbitrarily high rate.

0.40

Can you find the maximum throughput that can be achieved by distributing the $r$ robots among the $n$ stations optimally?

Input

Each case starts with $r$ and $n$. Follow the $n$ integers $p_1, \dots, p_n$, all between 1 and $10^9$. You can assume $1 \le n \le 10^5$ and $n \le r \le 10^9$.

Output

For every case, print the maximum possible throughput of the assembly line.