Background

Unlucky yyf always fails to draw the cards he wants, which makes him hate gacha. However, playing sif (a game) is impossible without gacha, so he consulted the lucky dew. Dew revealed the secrets of gacha to him, yet yyf still doesn't know how to maximize his luck. Therefore, he turns to you for help.

Problem Description

Dew told yyf that the luck value for each card draw is fixed, with the luck value of the $i$-th card being $a_i$. When drawing multiple cards consecutively, the luck value is equal to that of the first card in the sequence.

The "sum of luck values for each draw" refers to the sum of luck values for each single draw plus the sum of luck values for each consecutive draw. The luck value of a consecutive draw is not weighted; it is counted only once.

yyf wants to perform $c$ consecutive draws ($c$ cards in a row) $n$ times and single draws $m$ times. Since continuous single draws are tiring, yyf does not want to perform more than $d$ consecutive single draws (exactly $d$ consecutive single draws are allowed). There are a total of $c*n+m$ cards, and the order of drawing cannot be changed. Each card must be drawn exactly once, and only the decision of which cards to draw consecutively and which to draw singly can be changed. What is the maximum sum of luck values yyf can achieve for each draw, and how can it be achieved?

Input Format

The first line contains four positive integers $n$, $m$, $c$, and $d$.

The second line contains $c*n+m$ positive integers, where the $i$-th positive integer $a_i$ represents the luck value of the $i$-th card.

Output Format

The first line contains one positive integer representing the maximum sum of luck values for each draw.

The second line contains $n$ positive integers representing the indices of the first card in each consecutive draw. If there are multiple solutions, output any one of them. (If you cannot output a solution, please output $n$ random integers on the second line, otherwise, you may get $0$ points.)

The indices should be output in ascending order.

Sample Input and Output

Sample Input #1

3 3 3 3
2 7 1 4 5 3 6 8 5 1 2 9

Sample Output #1

36
2 5 9

Sample Input #2

2 5 2 2
7 3 3 7 7 5 1 10 2

Sample Output #2

41
2 6

Notes/Hints

$20\%$ of the data has $1 \le n \le 5$, $1 \le m \le 5$, $2 \le c \le 5$.

$50\%$ of the data has $1 \le n \le 40$, $1 \le m \le 200$, $2 \le c \le 20$.

Another $20\%$ of the data has $d=m$.

$100\%$ of the data has $1 \le n \le 40$, $1 \le m \le 80000$, $2 \le c \le 3000$, $1 \le a_i \le 10000$, $1 \le d \le m$, $d*(n+1) \ge m$.

There are $10$ test cases. Each test case will be scored as follows: $0$ points for an incorrect answer, $6$ points for a correct answer with an incorrect solution, and $10$ points for a correct answer with a correct solution.

Explanation of the sample: The output solution is explained in the sample.

Sample 1: Single draw $1$, consecutive draw $2$~$4$, consecutive draw $5$~$7$, single draw $8$, consecutive draw $9$~$11$, single draw $12$. The total luck value is $2+7+5+8+5+9=36$.

Sample 2: Single draw $1$, consecutive draw $2$~$3$, single draw $4$, single draw $5$, consecutive draw $6$~$7$, single draw $8$, single draw $9$. The total luck value is $7+3+7+7+5+10+2=41$.

It can be proven that the above two solutions are the ones with the highest total luck value under the given conditions.

见题面 Input 部分

见题面 Output 部分