외계인의 양말

면접 대비

시간 제한1초메모리 제한1024 MB

요약

여러 색 양말의 개수가 주어질 때, 한 색의 양말 k개를 반드시 갖게 되는 최소 추출 수를 구하고 불가능하면 -1을 출력한다.

문제

비트랜드에 외계인 우주선이 착륙했다. 외계인들은 비트랜드의 멋진 양말에 완전히 매료되었다. 외계인은 다리가 $k$ 개이기 때문에, 다양한 색깔의 양말을 아주 많이 사들였다.

외계인 브로늄스의 서랍에는 서로 다른 $s$ 가지 색의 양말이 들어 있고, 브로늄스는 각 색깔의 양말이 몇 짝씩 있는지를 모두 알고 있다. 매일 아침 브로늄스는 서랍을 보지 않고 양말을 한 짝씩 꺼내며, 같은 색 양말이 손에 $k$ 짝 모일 때까지 계속 꺼낸다.

오늘 아침 브로늄스는 매우 급해서, 손에 같은 색 양말이 반드시 $k$ 짝 모이도록 하려면 최소 몇 짝을 꺼내야 하는지 알고 싶어 한다.

첫째 줄에 두 양의 정수, 브로늄스의 다리 수 $k$ 와 서랍에 있는 양말 색의 수 $s$ 가 주어진다.

둘째 줄에 $s$ 개의 양의 정수 $n_i$ 가 주어지며, 이는 서랍에 있는 $i$ 번째 색 양말의 개수를 나타낸다.

브로늄스가 최소 몇 짝을 꺼내야 하는지를 나타내는 하나의 양의 정수를 출력한다. 같은 색 양말을 $k$ 짝 꺼내는 것이 불가능하다면 $-1$ 을 출력한다.