Balloon Factory

Interview

Time limit1sMemory limit256 MB

Summary

Find the minimum time for N workers, each producing one balloon every A_i minutes, to finish M balloons in parallel.

Level: Medium5 of 10
Topics: Binary search, Greedy, Math, Array
Solved: No attempts yet

Problem

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$ .

Input

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$ ).

Output

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

Hint

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.

Examples2

Example 1
Input
```
3 8
5 7 3
```
Expected output
```
14
```
Example 2
Input
```
1 5
7
```
Expected output
```
35
```