조삼모사

동물원에서 탈출한 원숭이가 일렬로 놓인 N개의 바나나를 모두 은신처로 옮기려고 한다.

원숭이는 두 가지 방법으로 바나나를 옮길 수 있다.

• 바나나 한 개를 옮긴다. 걸리는 시간은 그 바나나의 무게와 같다.
• 처음 놓인 순서에서 연속한 K개의 바나나를 한꺼번에 옮긴다. 걸리는 시간은 항상 C이다.

은신처에서 배급소로 돌아오는 데 걸리는 시간은 0초이다. 원숭이는 바나나를 들고 있지 않을 때 순간이동할 수 있기 때문이다.

N개 바나나의 무게가 주어질 때, 모든 바나나를 옮기는 데 필요한 최소 시간을 구하시오. 최소 시간이 되는 방법이 여러 가지라면, K개를 한꺼번에 옮기는 횟수가 가장 적은 방법을 선택해야 한다.

첫째 줄에 바나나의 개수 N이 주어진다. N은 1 이상 1,000,000 이하이다.

둘째 줄에 K와 C가 주어진다. K와 C는 각각 1 이상 10,000 이하이다.

셋째 줄에 바나나의 무게를 나타내는 N개의 자연수가 처음 놓인 순서대로 주어진다. 각 무게는 1 이상 1,000 이하이다.

첫째 줄에 모든 바나나를 옮기는 최소 시간을 출력한다.

둘째 줄에 K개를 한꺼번에 옮기는 횟수를 출력한다.

셋째 줄에는 그때 선택한 각 묶음의 왼쪽 위치를 오름차순으로 출력한다. 위치는 1부터 시작한다. 선택한 묶음이 없으면 빈 줄을 출력한다.

최소 시간과 최소 횟수를 모두 만족하는 방법이 여러 가지라면 아무 방법이나 출력해도 된다.