영화관 관람 지갑

문제

작은 영화관에서는 매일 한 편씩 상영하는 기획전을 연다. 한 관객은 기획전이 열리는 N일 동안 관람 전용 지갑을 사용하기로 했다. 지갑에는 처음에 돈이 없으며, i번째 날 아침에는 그날 준비한 금액 A_i원을 지갑에 넣는다. 전날 쓰고 남은 돈은 사라지지 않고 다음 날에도 그대로 사용할 수 있다. 기획전의 모든 영화표 가격은 P원으로 같다. 관객은 매일 아침 돈을 넣은 직후 지갑의 잔액을 확인한다. 잔액이 P원 이상이면 영화표를 정확히 한 장 구매하고, 지갑에서 P원을 뺀다. 잔액이 P원보다 적으면 그날은 영화표를 구매하지 않는다. 어느 날에도 영화표를 두 장 이상 사지 않으며, 잔액이 표 두 장의 가격보다 많더라도 한 장만 구매한다. 따라서 많은 돈이 남은 날에도 다음 날 사용할 잔액이 생길 수 있다. 영화표를 구매한 날에는 그날 상영하는 영화를 관람한다. 지난 날짜의 영화표를 뒤늦게 구매하거나, 다음 날의 영화표를 미리 구매하는 일은 없다. 돈을 넣은 뒤에는 위 규칙에 따라 구매 여부가 바로 결정되며, 관객이 임의로 구매를 미루거나 건너뛰는 일도 없다. 표를 구매할 때 지갑의 잔액이 정확히 P원이면 구매한 뒤 잔액은 0원이 된다. 각 날짜에 준비한 금액은 서로 다를 수 있고, 0원인 날도 있다. 그날 넣은 돈이 0원이더라도 이전 날짜부터 남아 있던 돈이 충분하면 표를 구매한다. 반대로 여러 날 동안 조금씩 넣은 돈이 모여야 처음으로 표를 살 수도 있다. 모든 날짜의 금액이 주어졌을 때, N일 동안 영화를 관람한 날의 수와 마지막 날의 구매 처리가 끝난 뒤 지갑에 남은 금액을 구한다.

입력

첫째 줄에 기획전이 열리는 날의 수 N과 영화표 가격 P가 주어진다. 1≤N≤1,000, 1≤P≤10,000이다.
둘째 줄에 A_1부터 A_N까지가 공백으로 구분되어 주어진다. 0≤A_i≤10,000이다. 입력의 모든 수는 정수이다.

출력

영화를 관람한 날의 수와 마지막 잔액을 한 줄에 공백으로 구분하여 출력한다. 한 번도 관람하지 못했다면 관람한 날의 수로 0을 출력한다.

5 7
3 4 0 15 0

3 1

4 10
0 2 3 4

0 9

3 5
15 0 0

3 0

출처: Devin.KR 자체 제작