Balloon Factory

There are $N$ staff members who share the work of making $M$ balloons. Staff member $i$ takes $A_i$ minutes to make one balloon and can start the next balloon immediately after finishing one. All staff members start working together at minute $0$. Find the minimum number of minutes needed until all $M$ balloons are finished. Balloon designs do not matter.

For example, a staff member who takes $5$ minutes per balloon and starts at minute $0$ finishes the first balloon at minute $5$ and the second balloon at minute $10$.

The first line contains the number of staff members $N$ and the number of balloons $M$ ($1 \le N, M \le 1\,000\,000$).

The second line contains $N$ integers, the time $A_i$ in minutes each staff member takes to make one balloon ($1 \le A_i \le 1\,000\,000$).

Print a single integer, the minimum number of minutes needed to finish all $M$ balloons.

Whether a candidate time of $T$ minutes is enough can be counted directly. Staff member $i$ finishes $\lfloor T / A_i \rfloor$ balloons within $T$ minutes, so $M$ balloons can be finished within $T$ minutes when the total over all staff members is at least $M$. Binary-searching the range of possible times with this check gives the minimum time.