좌석 배치

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

요약

학교 K개의 학생 수가 주어질 때, 전체 학생을 M개 방에 최대한 고르게 나눴을 때 한 방의 최대 인원을 구합니다.

난이도: 쉬움10점 중 2점
유형: 수학, 구현
정답자: 아직 제출이 없습니다

문제

올림피아드 준비에는 문제 작성, 테스트 제작, 해설 작성, 컴퓨터 설정 등 할 일이 많아서 참가자를 강의실에 올바르게 배정하는 일을 잊기 쉽습니다. 이번에는 좌석을 효율적으로 쓰려고 운영위원회가 학생들을 $M$ 개의 강의실에 컴팩트하게 배정하려 합니다. 임의의 서로 다른 두 강의실에 있는 아이들의 수 차이가 1 이하이면 그 배정을 컴팩트하다고 합니다. 심사위원 중 한 명이 $K$ 개 학교의 학생들이 본선에 진출할 것이라고 예측했습니다. 또한 $i$ 번째 학교에서 정확히 $n_i$ 명이 온다고 예측했습니다 ( $1 \le i \le K$ ). 위원회의 많은 사람은 이런 예측에 회의적이지만, 예측이 맞아떨어지는 경우가 있습니다. 예측이 맞다고 가정할 때, 컴팩트한 배정에서 한 강의실에 들어갈 수 있는 참가자 수의 최댓값을 구하세요.

입력

첫 줄에 두 정수 $M$ 과 $K$ 가 주어집니다. $M$ 은 강의실 수, $K$ 는 학교 수입니다 ( $1 \le M \le 10^9$ , $1 \le K \le 100000$ ). 둘째 줄에는 공백으로 구분된 $K$ 개의 정수 $n_1, n_2, \ldots, n_K$ 가 주어집니다 ( $1 \le n_i \le 10^9$ ).

출력

컴팩트한 배정에서 한 강의실에 들어갈 수 있는 참가자 수의 최댓값을 한 줄에 출력하세요.

힌트

첫 번째 테스트에서는 컴팩트한 배정이 하나뿐이며, 두 강의실에 각각 7명씩 배정됩니다.

예제2

예제 1
입력
```
2 2
5 9
```
예상 출력
```
7
```
예제 2
입력
```
1 2
20 10
```
예상 출력
```
30
```