대관람차

Singapore Flyer © CEphoto, Uwe Aranas

공항을 통과하는 매우 잘 최적화된 경로를 따라간 끝에, 스웨덴 대표팀은 마침내 싱가포르의 IOI에 도착했다. 첫 번째 견학에서 IOI의 모든 $N$개 팀은 거대한 대관람차 Singapore Flyer를 타게 된다. 대관람차에는 $M$개의 객차가 있으며, 바퀴가 한 바퀴 도는 데 $M$분이 걸린다 (즉, 각 객차가 한 칸 이동하는 데 1분이 걸린다).

어떤 팀들은 다른 팀들보다 대관람차를 타는 데 더 관심이 있는 듯하며, 따라서 각 팀은 정확히 몇 바퀴를 타고 싶은지 정할 수 있다. 참가자들이 원하는 바퀴 수를 모두 타기 전에 내렸다가 다시 타야 한다면 지루할 것이다. 따라서 한 팀이 객차에 일단 탑승하면, 원하는 바퀴 수를 모두 탈 때까지 그 객차에 계속 앉아 있을 수 있도록 정해졌다. 이는 바퀴가 돌아 객차 하나가 입구로 내려왔지만 계속 타고 싶어 하는 팀이 이미 그 객차에 앉아 있다면, 다음 팀은 그 객차에 탈 수 없다는 뜻이다. 그러면 이 팀은 빈 객차나 내리는 팀이 있는 객차를 기다려야 한다.

팀들은 객차에 타고 내리는 데 매우 능숙하므로, 가장 아래쪽 객차에서 팀이 교대하는 데 추가 시간은 걸리지 않는다.

현재 모든 팀은 대관람차 앞에 줄을 서 있으며, 스웨덴 대표팀은 모두가 타는 데 얼마나 오래 걸릴지 궁금해한다.

점수

여러 테스트 케이스 그룹으로 풀이를 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$    |$20$|  $1 \leq N, M, T_i \leq 100$

$2$    |$30$|  $1 \leq N, M, T_i \leq 1000$

$3$    |$25$|  $1 \leq N, M \leq 1000$

$4$    |$25$|  추가 제한 없음.

첫 번째 줄에는 정수 $N$와 $M$가 주어진다 ($1 \leq N,M \leq 2 \cdot 10^5$). 이는 각각 팀의 수와 대관람차 객차의 수이다.

두 번째 줄에는 $N$개의 정수 $T_1, \dots , T_N$가 주어진다 ($1 \leq T_i \leq 10^9$). 여기서 $T_i$는 번호가 $i$인 팀이 타고 싶어 하는 바퀴 수이다. 팀들은 줄에서의 위치 순으로 정렬되어 있으며, $T_1$가 줄의 맨 앞 팀이다.

모든 팀이 타는 데 걸리는 시간(분)을 나타내는 정수 하나를 한 줄에 출력한다.

예제 1

예제 $1$에는 $4$개 팀과 $3$개 객차가 있다. 그림에서 각각 스웨덴, 노르웨이, 핀란드, 덴마크인 팀들은 각각 $2$, $2$, $1$, $1$바퀴를 타고 싶어 한다. 덴마크 팀은 $t=3$ 또는 $t=4$에 대관람차에 탈 수 없다는 점에 유의하라. 두 경우 모두 스웨덴 / 노르웨이 팀이 이미 가장 아래쪽 객차에 앉아 있으며 한 바퀴 더 타고 싶어 하기 때문이다.