시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB (추가 메모리 없음)186323136.471%

문제

컴퓨터과학과의 교수님들은 학생들을 기쁘게 하기 위해 과제를 비슷한 시기에 내주신다.

이번 학기 $6$전공을 채워 넣은 태호는 교수님들의 과제 공격을 받고 정신을 못 차리고 있다.

각각의 과제는 $X_i$ 일 동안 하면 마무리가 되는데, 태호는 이틀 연속으로 똑같은 과목의 과제를 하면 일찍 질려버린다. 결국 태호는 매일 매일 다른 과목의 과제를 하기로 결정했다. 만약 $N$개의 과제를 해야 한다면, $1$일 차엔 첫 번째 과제를 하고, $2$일 차에는 두 번째 과제를 하고, ... $N$일차에는 $N$번째 과제를 한 후, 다시 $N + 1$일차에 첫 번째 과제를 하는 것을 반복하려고 한다.

단, 쉬는 날 없이 과제만 하게 되면 과로사를 할 수 있음으로, $M - 1$일 동안 과제를 하고 $M$일차에 휴식을 취하는 것을 반복할 것이다. 그러나 쉬는 날에 원래 해야 할 과제가 있다면, 그 과제를 다음날로 미루지 않고 아예 하지 않고 넘어갈 것이다.

예를 들어, $5$개의 과제가 있고 $4$일에 한 번씩 쉰다고 가정하면, $1$일 차에는 $1$번 과제를, $2$일 차에는 $2$번 과제를, $3$일 차에는 $3$번 과제를 수행한다. $4$일 차에는 $4$번 과제를 수행해야 하나, 휴식일이기 때문에 수행하지 않고 넘어간다. 대신, $5$일 차에는 $4$번 과제가 아닌 $5$번 과제를 수행해야 한다.

만족스러운 플랜을 짰다고 생각해 스스로 만족한 태호였으나, 막상 만들고 보니 과제를 언제 끝낼 수 있을지 궁금해졌다.

과제를 완료하는데 필요한 날의 정보와 휴식일의 정보가 주어질 때, 가장 먼저 끝나는 과제를 구해보자.

입력

첫 줄에는 $N$과 $M$이 주어진다. ($2 \le N \le 20\ 000$, $2 \le M \le 500$)

두 번째 줄에 $X_1$, $X_2$, ..., $X_N$가 공백으로 구분되어 주어진다. ($1 \le X_i \le 125\ 000\ 000$)

출력

태호가 가장 먼저 끝내는 과제의 번호를 출력한다.

예제 입력 1

5 7
4 2 2 3 5

예제 출력 1

3

태호는 다음과 같은 방법으로 과제를 진행한다.

  • 1일차에 1번 과제를 수행한다. 이제 남은 과제의 양은 $[3, 2, 2, 3, 5]$가 된다.
  • 2일차에 2번 과제를 수행한다. 이제 남은 과제의 양은 $[3, 1, 2, 3, 5]$가 된다.
  • 3일차에 3번 과제를 수행한다. 이제 남은 과제의 양은 $[3, 1, 1, 3, 5]$가 된다.
  • 4일차에 4번 과제를 수행한다. 이제 남은 과제의 양은 $[3, 1, 1, 2, 5]$가 된다.
  • 5일차에 5번 과제를 수행한다. 이제 남은 과제의 양은 $[3, 1, 1, 2, 4]$가 된다.
  • 6일차에 1번 과제를 수행한다. 이제 남은 과제의 양은 $[2, 1, 1, 2, 4]$가 된다.
  • 7일차에 2번 과제를 수행해야 하나, 이 날은 태호가 쉬는 날이기 때문에 과제를 하지 않는다. 남은 과제의 양은 6일차와 동일하게 $[2, 1, 1, 2, 4]$ 이다.
  • 8일차에 3번 과제를 수행한다. 이제 남은 과제의 양은 $[2, 1, 0, 2, 4]$가 된다.

8일차에 3번 과제를 모두 수행했으므로, 답은 $3$이 된다.

예제 입력 2

7 7
10 9 8 4 5 6 1

예제 출력 2

4

출처

University > 연세대학교 > 2021 연세대학교 프로그래밍 경진대회 H번