프로세스

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

요약

N개의 작업 큐와 K번의 프로세스 분할 한도가 주어질 때, 프로세스마다 초당 작업 하나를 처리한다고 할 때 모든 작업을 끝내는 최소 시간을 구한다.

문제

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

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

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

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

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

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

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

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

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