Batteries

On the day of the competition, the laboratory uses $n$ computers. Unfortunately, the electricity is turned off, and the computers can only work on batteries. The technical staff of the competition has $m$ batteries. The $i$-th battery allows any computer to work for $a_i$ minutes.

Initially, they can fit no more than one battery per computer. After that, at any minute, you can remove the current battery from any computer and insert another one. The inserted battery can be either new or taken from another computer. You can assume that the process of removing and installing the battery takes no time. Also, note that batteries are not rechargeable.

To determine the duration of the competition, the organizers want to know the maximum number of minutes during which all computers can be used simultaneously. It is quite difficult for the technical staff to determine this. Help them with this.

Input

The first line contains two integers $n$ and $m(1\le n\le m\le 10^5)$ — the number of computers and batteries, respectively. The next line contains $m$ integers $a_1,a_2,...,a_m(1\le a_i\le 10^9,1\le i\le m)$ — the capacity of the batteries.

Output

Output an integer — the maximum number of minutes during which all computers can work simultaneously.

Examples

In this example, there are $2$ computers and $3$ batteries. Each battery has a capacity of $3$ minutes. Initially, we place the first and second batteries in the first and second computers, respectively. After $2$ minutes, remove the battery from the first computer and insert the third battery (still fully charged) into the first computer. At the end of the $3$rd minute, the battery in the second computer will discharge, let's remove it and replace it with the first battery that we removed from the first computer, which still has $1$ minute left. At the end of the $4$th minute, this battery will also discharge. Although the first computer's battery currently has $1$ minute left, the other batteries are already discharged, and we can no longer sustain the operation of both computers.

Scoring

This problem consists of $5$ subtasks. Points for a subtask are awarded only if all the tests associated with that subtask are passed successfully.

1. ($5$ points): $a_i=1$;

2. ($6$ points): $n=m$;

3. ($14$ points): $a_i\le 2$;

4. ($17$ points): $n=2$;

5. ($58$ points): $noadditionalconstraints$;