외계인의 양말

면접 대비

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

요약

색깔별 양말 개수가 주어질 때, 한 색깔의 양말을 k개 이상 반드시 갖게 되는 최소 뽑기 횟수를 구한다.

문제

비트랜드에 외계인 우주선이 착륙했다. 외계인들은 비트랜드의 세련된 양말에 특히 매료되었다. 외계인은 다리가 $k$ 개이므로, 여러 색깔의 양말을 아주 많이 사들였다.

외계인 브로니우스의 서랍에는 서로 다른 $s$ 가지 색의 양말이 들어 있고, 각 색깔별 양말 개수도 알고 있다. 매일 아침 브로니우스는 서랍 안을 보지 않고 양말을 한 짝씩 꺼내며, 같은 색 양말 $k$ 짝을 손에 쥘 때까지 이를 반복한다.

오늘 아침 브로니우스는 몹시 바빠서, 같은 색 양말을 반드시 $k$ 짝 이상 손에 쥐려면 최소 몇 짝을 꺼내야 하는지 알고 싶어 한다.

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

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

브로니우스가 꺼내야 하는 최소 양말 짝 수인 양의 정수 하나를 출력한다. 브로니우스는 항상 충분한 양말을 꺼낼 수 있다.