Processes

Time limit1sMemory limit1024 MB

Summary

Given N queues of tasks, a limited number K of process splits, and one task completed per process per second, find the minimum time to finish all tasks.

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

Problem

Kolja has started working seriously on theoretical physics, and for his thesis he needs to run a large number of computations on a supercomputer. Each computation is called a task. The tasks are split into groups called queues, and each queue is handed to a separate process to compute.

The processes run in parallel. During each second, every process can perform exactly one of the following two actions:

Complete one task from its current queue.
Create a new process and hand part of its queue to it. For example, if a queue holds 10 tasks, the process may give 3 of them to the new process when creating it and keep the remaining 7 for itself.

Because of the operating system's own overhead, the total number of new-process creations is limited to $K$ (once a process has finished its work it cannot be restarted or reused in any other way).

Find the minimum number of seconds needed to complete all tasks.

Input

The first line contains the maximum allowed number of new-process creations $K$ .

The second line contains the initial number of processes $N$ .

Each of the next $N$ lines contains one integer $A_i$ , the number of tasks in the queue of the $i$ -th initial process ( $1 \le A_i \le 10^9$ ).

Output

Print the minimum number of seconds required to complete all tasks.

Examples2

Example 1
Input
```
3
3
6
6
5
```
Expected output
```
4
```
Example 2
Input
```
4
6
12
5
6
2
6
8
```
Expected output
```
6
```