dlaud5379   9달 전

(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

JAG(Japan Amusement Group)는 많은 관광객들이 찾아오는 놀이공원으로, 그 중에서도 롤러코스터는 특히 인기가 좋은 어트랙션이다.

오늘도 대성황을 이루고 있는 JAG의 롤러코스터 앞에는 수많은 단체 손님들이 줄을 서서 차례를 기다리고 있다. 현재 대기열에는 N팀의 단체 손님이 있으며, 그 중 i번째 팀은 ai명으로 이루어져 있다.

롤러코스터는 한 번 운행할 때마다 최대 M명까지 탑승할 수 있으며, 당신은 놀이공원의 스태프로서 롤러코스터가 운행할 때마다 다음 규칙에 따라 손님을 탑승시킨다. 이 과정을 대기열에 손님이 남지 않을 때까지 반복한다.

  1. 대기열이 비어 있거나, 대기열 맨 앞에 있는 팀의 인원수가 롤러코스터의 빈 좌석 수보다 많을 경우, 롤러코스터를 출발시킨 뒤 운행을 마칠 때까지 기다린다.
  2. 그렇지 않을 경우, 대기열 맨 앞에 있는 팀 전원을 롤러코스터의 빈 좌석에 탑승시킨다.
  3. 1번으로 돌아간다.

JAG의 폐장 시간이 임박했기 때문에, 당신은 인접한 팀끼리 대기 순서를 최대 한 번 바꾸어서 롤러코스터의 운행 횟수를 줄일 수 없을지 고민하고 있다. 구체적으로 당신은 다음 동작을 최대 한 번 수행할 수 있다.

  • 1 ≤ i ≤ N-1을 만족하는 어떤 정수 i에 대해, 대기열의 i번째 팀과 i+1번째 팀의 대기 순서를 바꾼다.

위의 동작을 최적으로 수행했을 때, 대기열의 모든 손님을 수용하는 데 필요한 롤러코스터 운행 횟수의 최솟값을 구하는 프로그램을 작성하여라. 대기열에 새로운 팀이 추가되거나 기존 팀이 대기열에서 벗어나는 경우는 생각하지 않는다.

입력

입력은 50개 이하의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 다음과 같이 주어진다.

N M
a1 a2 ... aN

첫째 줄에는 대기열에 있는 팀의 수 N과 롤러코스터의 정원 M이 주어진다. (2 ≤ N ≤ 2×105, 1 ≤ M ≤ 109)

둘째 줄에는 N개의 정수 a1, a2, ..., aN이 주어진다. 이때 ai는 대기열의 i번째 팀의 인원수이다. (1 ≤ ai ≤ M)

모든 테스트 케이스에 걸쳐 N의 합은 2×106 이하이다.

입력의 끝에는 0이 두 개 주어진다.

출력

각 테스트 케이스마다 문제의 정답을 한 줄로 출력한다.

댓글을 작성하려면 로그인해야 합니다.