안내판을 여는 순서

문제

한 주차장은 입구에서 안쪽으로 이어지는 N개의 구역으로 나뉘어 있다. 구역에는 입구에 가까운 순서대로 1번부터 N번까지 번호가 붙어 있으며, 모든 구역에는 주차 칸이 정확히 C개씩 있다. 관리인은 안내판을 켜서 새로 들어오는 차량이 이용할 수 있는 구역을 표시하려 한다. 점검을 마친 결과 i번 구역에는 이미 A_i대의 차량이 주차되어 있다. 차량 한 대는 주차 칸 하나를 차지하며, 나머지 칸은 모두 이용할 수 있다. 안내판의 연결 방식 때문에 구역을 임의로 골라 열 수는 없다. 관리인은 반드시 1번 구역부터 번호가 증가하는 순서대로 구역을 열어야 한다. 따라서 마지막으로 연 구역이 p번이라면 1번부터 p번까지의 구역이 모두 열리고, p번보다 뒤에 있는 구역은 모두 닫혀 있다. 구역 하나를 열 때에는 그 구역의 빈 주차 칸이 한꺼번에 모두 이용 가능한 상태가 된다. 한 구역에서 일부 칸만 따로 열 수는 없다. 관리인은 새로 들어올 차량을 위해 빈 주차 칸을 적어도 K개 확보하려 한다. 안내가 복잡해지는 것을 줄이기 위해, 이 조건을 만족하는 순간 더 이상 구역을 열지 않는다. 여기서 확보한 칸의 수는 열린 구역에 있는 빈 칸의 합이며, 이미 주차된 차량이 차지한 칸은 포함하지 않는다. 빈 칸이 하나도 없는 구역도 순서에 따라 열어야 하며, 이러한 구역을 건너뛰어 번호를 줄일 수는 없다. 점검과 안내판 설정이 진행되는 동안 차량이 들어오거나 나가는 일은 없다. 조건을 만족하도록 열어야 하는 최소 구역 수와, 그때 확보한 빈 칸 중 K개를 제외하고 남는 칸 수를 구한다. 모든 구역을 열어도 빈 칸이 K개보다 적다면 확보가 불가능하다고 판단한다.

입력

첫째 줄에 정수 N, C, K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000, 1 ≤ C ≤ 9, 1 ≤ K ≤ 900,000이다.
둘째 줄에 각 구역에 주차된 차량 수를 나타내는 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ A_i ≤ C이다.

출력

빈 주차 칸을 적어도 K개 확보할 수 있다면, 열어야 하는 최소 구역 수 p와 그때 확보한 빈 칸 수에서 K를 뺀 값을 공백으로 구분하여 출력한다. 최소 구역 수는 유일하게 정해진다. 모든 구역을 열어도 확보할 수 없다면 -1만 출력한다.

6 5 9
4 2 5 1 3 0

5 1

4 3 5
3 2 3 1

-1

1 9 1
0

1 8

출처: Devin.KR 자체 제작