Delegation Check-in Optimization

A delegation of m members from a certain country is headed to the 2013 IOI in Australia. They are currently waiting in line at the airport to complete their check‐in process. There are n service counters available for check‐in. The counters operate at different speeds; at the k-th counter, processing a passenger takes $t_k$ seconds.

Initially, all counters are idle and ready to process the next passenger. However, only the delegation members are allowed to queue. A person can only step forward if all those ahead of him have started their check-in process (they do not necessarily have to finish processing at that moment). When eligible, the person may immediately take an available counter or decide to wait for a faster counter to become available.

The delegation members, being computer science wizards, want everyone to start their check-in as soon as possible. Your task is to find the minimum time needed for all members to begin their check-in process.

Note: A counter can serve one passenger immediately at time 0. After that, the same counter can serve additional passengers at times that are integer multiples of its processing time. Formally, a counter with time $t_k$ can serve a new passenger at time 0, $t_k$, $2t_k$, $3t_k$, and so on.

If m ≤ n, then every member can start immediately at time 0.

The problem can be solved using binary search.

inputFormat

The first line contains two integers m and n (1 ≤ m, n ≤ 10⁹), representing the number of delegation members and the number of service counters, respectively.

The second line contains n space-separated positive integers: t₁, t₂, ..., t_n (1 ≤ t_k ≤ 10⁹), where t_k is the number of seconds required for counter k to process one passenger.

outputFormat

Output a single integer: the minimum number of seconds required for all m delegation members to begin their check-in.

sample

6 2
3 5

9