Alien Socks

Interview

Time limit1sMemory limit1024 MB

Summary

Given counts of socks in s colors, find the smallest number of socks to draw to guarantee k socks of one color, or -1 if impossible.

Level: Easy3 of 10
Topics: Math, Greedy, Array
Solved: No attempts yet

Problem

An alien spaceship has landed in Bitland. The aliens were completely charmed by Bitland's fashionable socks. Because each alien has $k$ legs, they bought a huge number of socks in many different colors.

The alien Bronius keeps socks of $s$ different colors in his drawer, and he knows exactly how many socks of each color he has. Every morning Bronius pulls socks out of the drawer one at a time without looking, and he keeps going until he holds $k$ socks of the same color.

This morning Bronius is in a great hurry and wants to know the minimum number of socks he must pull out so that he is guaranteed to hold at least $k$ socks of one color.

Input

The first line contains two positive integers: Bronius's number of legs $k$ and the number of sock colors in the drawer $s$ .

The second line contains $s$ positive integers $n_i$ , where $n_i$ is the number of socks of the $i$ -th color in the drawer.

Output

Output a single positive integer — the minimum number of socks Bronius must pull out. If it is impossible for Bronius to ever collect $k$ socks of one color, output $-1$ .

Constraints

$1 \le k \le 1\,000$
$1 \le s \le 1\,000$
$1 \le n_i \le 1\,000$ for all $i$ .

Examples2

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