P4852 yyf hates choukapai

Unlucky yyf can never draw the cards he wants, so he also really hates drawing cards. But when playing sif, it is impossible to avoid drawing cards, so he went to consult the lucky dew. dew told him the secret of drawing cards, but yyf still did not know how to make his luck as high as possible, so he came to you.

dew tells yyf that when a person draws each card, the luck value is fixed. The luck value of the $i$-th card is $a_i$. When doing a consecutive draw, the luck value equals the luck value of the first card in that consecutive draw. “The sum of luck for each draw operation” means: the sum of luck from every single draw plus the sum of luck from every consecutive draw. For one consecutive draw, its luck is not weighted; it is counted only once. yyf wants to do $c$-card consecutive draws (draw $c$ consecutive cards) for $n$ times, and single draws for $m$ times. Because doing single draws all the time is too tiring, **yyf does not want to do more than $d$ consecutive single draws (doing exactly $d$ consecutive single draws is allowed)**. There are $c \times n + m$ cards in total. The drawing order cannot be changed. Each card must be drawn exactly once. You may only change which cards are drawn as consecutive draws and which are drawn as single draws. Then, what is the maximum possible sum of luck for all draw operations, and how can it be achieved?

Line $1$ contains $4$ positive integers $n, m, c, d$. Line $2$ contains $c \times n + m$ positive integers, where the $i$-th integer $a_i$ represents the luck value of the $i$-th card.

Line $1$ outputs one positive integer representing the maximum possible sum of luck for yyf’s draw operations. Line $2$ outputs $n$ positive integers representing the indices of the first card of each consecutive draw. If there are multiple valid solutions, output any one. (If you cannot output a solution, please still output any $n$ integers on the second line, otherwise you may get $0$ points.) Output the indices in increasing order.

For $20\%$ of the testdata, $1 \le n \le 5$, $1 \le m \le 5$, $2 \le c \le 5$. For $50\%$ of the testdata, $1 \le n \le 40$, $1 \le m \le 200$, $2 \le c \le 20$. Another $20\%$ of the testdata has $d = m$. For $100\%$ of the testdata, $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 \times (n + 1) \ge m$. There are $10$ test points in total. For each test point: if the answer is wrong, you get $0$ points; if the answer is correct but the plan is wrong, you get $6$ points; if both the answer and the plan are correct, you get $10$ points. Sample explanation: the output plan is exactly the sample explanation QAQ. Sample 1: single draw $1$, consecutive draw $2 \sim 4$, consecutive draw $5 \sim 7$, single draw $8$, consecutive draw $9 \sim 11$, single draw $12$. The total luck sum is $2 + 7 + 5 + 8 + 5 + 9 = 36$. Sample 2: single draw $1$, consecutive draw $2 \sim 3$, single draw $4$, single draw $5$, consecutive draw $6 \sim 7$, single draw $8$, single draw $9$. The total luck sum is $7 + 3 + 7 + 7 + 5 + 10 + 2 = 41$. It can be proven that, under the constraints, the above two plans achieve the maximum possible total luck sum. Translated by ChatGPT 5