Morning Three and Evening Four

A monkey that escaped from a zoo wants to move all N bananas placed in a line to its hideout.

The monkey can move bananas in two ways.

• Move one banana. This takes time equal to that banana's weight.
• Move K bananas that are consecutive in the original order at once. This always takes C seconds.

Returning from the hideout to the distribution place takes 0 seconds, because the monkey can teleport when it is not carrying bananas.

Given the weights of the N bananas, find the minimum time needed to move every banana. If several plans achieve the minimum time, choose one that uses the fewest grouped moves of K bananas.

The first line contains the number of bananas N. N is an integer between 1 and 1,000,000, inclusive.

The second line contains K and C. Each of K and C is an integer between 1 and 10,000, inclusive.

The third line contains N positive integers, the banana weights in their original order. Each weight is between 1 and 1,000, inclusive.

Print the minimum time needed to move every banana on the first line.

Print the number of grouped moves of K bananas on the second line.

On the third line, print the leftmost positions of the chosen groups in increasing order. Positions are 1-indexed. If no group is chosen, print an empty line.

If several plans satisfy both the minimum time and the minimum number of grouped moves, any one of them may be printed.