학원의 과제 도장판

문제

한 학원은 학생이 매 수업일의 과제를 제출했는지 확인하고 도장판을 관리한다. 도장판에는 아직 교환에 사용하지 않은 도장이 놓인다. 기록을 시작할 때 도장판은 비어 있고, 학생이 받은 교환권도 없다. 학원은 N번의 수업이 끝날 때마다 그날의 과제 제출 여부를 한 번씩 기록한다. 학생이 그날 과제를 제출했으면 도장판에 도장 하나를 추가한다. 추가한 직후 도장 수가 K개가 되면 즉시 교환권 한 장을 지급하고 도장판의 도장 K개를 모두 지운다. 이때 교환권을 지급한 날의 도장을 새 도장판에 다시 찍지는 않는다. 다음 수업일은 도장이 없는 상태에서 시작한다. K가 1이면 과제를 제출할 때마다 교환권 한 장을 받고 도장판은 곧바로 비워진다. 학생이 그날 과제를 제출하지 않았으면 도장판에 남아 있던 도장을 모두 지운다. 이미 받은 교환권은 과제를 제출하지 않은 날에도 사라지지 않는다. 도장판이 비어 있을 때 과제를 제출하지 않아도 도장 수는 그대로 0이다. 하루의 기록은 제출 또는 미제출 중 하나이며, 과제를 여러 개 제출하더라도 이 기록에서는 제출 한 번으로만 취급한다. 각 기록은 실제 수업이 진행된 순서대로 주어진다. 기록에 포함되지 않은 날짜에 대해서는 도장을 추가하거나 지우지 않는다. 모든 기록을 처리한 뒤 받은 교환권의 총장수와 도장판에 남은 도장 수를 구한다. 교환권을 받을 수 없었던 경우에는 교환권 수를 0으로 출력한다. 마지막 기록을 처리한 직후에도 교환 조건을 즉시 적용하므로, 최종적으로 남는 도장 수는 항상 K보다 작다. 학생은 한 명뿐이며 다른 학생의 기록과 비교하거나 동점을 처리할 필요는 없다.

입력

첫째 줄에 수업 기록 수 N과 교환에 필요한 도장 수 K가 공백으로 구분되어 주어진다. 둘째 줄에 기록 X_1, X_2, …, X_N이 공백으로 구분되어 주어진다. X_i가 1이면 i번째 수업일에 과제를 제출했고, 0이면 제출하지 않았다는 뜻이다. 모든 값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000, X_i ∈ {0, 1}이다.

출력

받은 교환권의 총장수와 마지막 기록 처리 후 남은 도장 수를 공백으로 구분하여 한 줄에 출력한다.

9 3
1 1 1 1 0 1 1 1 1

2 1

5 4
1 1 0 1 1

0 2

4 1
1 0 1 1

3 0

출처: Devin.KR 자체 제작