프로세스

Kolja는 이론물리학을 본격적으로 연구하기 시작했고, 졸업 논문을 위해 슈퍼컴퓨터에서 수많은 계산을 수행해야 한다. 각 계산을 하나의 작업이라고 부른다. 작업들은 여러 개의 대기열로 나뉘며, 각 대기열은 계산을 위해 별도의 프로세스에 할당된다.

프로세스들은 병렬로 동작한다. 매 초마다 각 프로세스는 다음 두 가지 동작 중 정확히 하나를 수행할 수 있다.

• 현재 대기열에 있는 작업 하나를 처리한다.
• 새로운 프로세스를 생성하고, 자신의 대기열 일부를 그 프로세스에 넘긴다. 예를 들어 대기열에 작업이 10개 있다면, 새 프로세스를 만들 때 그중 3개를 새 프로세스에 주고 나머지 7개는 자신이 가질 수 있다.

운영체제 자체의 부담 때문에, 새로 생성할 수 있는 프로세스의 총 개수는 $K$개로 제한된다(작업을 끝낸 프로세스는 다시 시작하거나 다른 어떤 방식으로도 재사용할 수 없다).

모든 작업을 끝내는 데 필요한 최소 초 수를 구하여라.

첫째 줄에는 새로 생성할 수 있는 프로세스의 최대 개수 $K$가 주어진다.

둘째 줄에는 처음 프로세스의 개수 $N$이 주어진다.

다음 $N$개의 줄에는 각각 정수 $A_i$가 주어지며, 이는 $i$번째 초기 프로세스의 대기열에 있는 작업의 개수이다 ($1 \le A_i \le 10^9$).

모든 작업을 끝내는 데 필요한 최소 초 수를 출력한다.