School Concert

Interview

Time limit1sMemory limit1024 MB

Summary

Given K burners with different speeds and N discs to burn, find the minimum time to finish all discs when each burner works continuously.

Level: Medium6 of 10
Topics: Binary search, Greedy, Math, Implementation
Solved: No attempts yet

Problem

An informatics teacher wants to record a video of the school concert onto N DVDs. He has access to a computer room containing K computers with burners. The video file has already been copied to every computer.

Unfortunately, the computers were made at different times and have different hardware, so the burners run at different speeds.

Write a program concert that finds the minimum time needed to burn all the DVDs.

Input

The first line of the standard input contains the two integers N and K.

The next line contains K integers T1, T2, ..., Tk: the time in minutes needed to burn one disc on the corresponding computer.

The numbers are separated by a single space.

Output

On one line of the standard output the program must print a single integer: the minimum number of minutes needed to burn all the discs.

Constraints

1 ≤ N, K ≤ 105
1 ≤ Ti ≤ 105

Examples1

Example 1
Input
```
3 2
10 15
```
Expected output
```
20
```