yyf hates choukapai

题目背景

非酋yyf总是抽不到自己想要的卡,因此还十分讨厌抽卡。但玩sif不可能不抽卡,于是他去请教了一下欧皇dew。dew告诉了他关于抽卡的秘密,然而yyf还是不知道如何让自己欧气尽量地大,于是他找到了你。

题目描述

dew告诉yyf,人在抽每张卡时欧气值都是固定的,第 $i$ 张卡的欧气值为 $a_i$ ,而在连抽时,欧气值等于第一张卡的欧气值。 “每次抽卡的欧气之和”指每次单抽的欧气之和加上每次连抽的欧气之和,一次连抽的欧气不加权,只计算一次 yyf想 $c$ 连抽(连续抽 $c$ 张卡) $n$ 次,单抽 $m$ 次,因为一直单抽太累,**yyf不想连续单抽超过 $d$ 次(可以连续单抽恰好 $d$ 次)**。共有 $c*n+m$ 张卡,抽卡的顺序不能改变,每张卡都必须且只能抽一次,只能改变哪几张卡连抽、哪几张卡单抽。那么yyf每次抽卡的欧气之和最多能达到多少,又如何实现呢?

输入输出格式

输入格式


第 $1$ 行 $4$ 个正整数 $n\ m\ c\ d$ 第 $2$ 行 $c*n+m$ 个正整数,其中第 $i$ 个正整数 $a_i$ 代表第 $i$ 张卡的欧气值

输出格式


第 $1$ 行一个正整数代表yyf每次抽卡的欧气之和的最大值 第 $2$ 行 $n$ 个正整数代表每次连抽的第一张卡的编号,如果有多种方案满足要求任意输出一种 (如果不会输出方案也请在第二行随意输出 $n$ 个整数,否则可能 $0$ 分) 方案请升序输出

输入输出样例

输入样例 #1

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

输出样例 #1

36
2 5 9

输入样例 #2

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

输出样例 #2

41
2 6 

说明

$20\%$的数据有$1 \le n \le 5$,$1 \le m \le 5$,$2 \le c \le 5$ $50\%$的数据有$1 \le n \le 40$,$1 \le m \le 200$,$2 \le c \le 20$ 另有$20\%$的数据有$d=m$ $100\%$的数据有$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$ 共 $10$ 个测试点,每个测试点答案错误 $0$ 分,答案正确方案错误 $6$ 分,答案正确方案正确 $10$ 分。 样例解释:输出的方案就是样例解释了QAQ 样例一:单抽 $1$ ,连抽 $2$~$4$,连抽 $5$~$7$,单抽 $8$,连抽 $9$~$11$,单抽 $12$,欧气值总和为 $2+7+5+8+5+9=36$ 样例二:单抽 $1$ ,连抽 $2$~$3$,单抽 $4$,单抽 $5$,连抽 $6$~$7$,单抽 $8$,单抽 $9$,欧气值总和为 $7+3+7+7+5+10+2=41$ 可以证明在满足条件的情况下上述两种方案是欧气值总和最大的