You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

题目描述

dew 告诉 yyf，人在抽每张卡时欧气值都是固定的，第 $i$ 张卡的欧气值为 $a_i$，而在连抽时，欧气值等于第一张卡的欧气值。

“每次抽卡的欧气之和”指每次单抽的欧气之和加上每次连抽的欧气之和，一次连抽的欧气不加权，只计算一次。

yyf 想 $c$ 连抽（连续抽 $c$ 张卡）$n$ 次，单抽 $m$ 次，因为一直单抽太累，yyf 不想连续单抽超过 $d$ 次（可以连续单抽恰好 $d$ 次）。共有 $c\times n+m$ 张卡，抽卡的顺序不能改变，每张卡都必须且只能抽一次，只能改变哪几张卡连抽、哪几张卡单抽。那么 yyf 每次抽卡的欧气之和最多能达到多少，又如何实现呢？

输入格式

第 $1$ 行 $4$ 个正整数 $n,m,c,d$。

第 $2$ 行 $c\times n+m$ 个正整数，其中第 $i$ 个正整数 $a_i$ 代表第 $i$ 张卡的欧气值。

输出格式

第 $1$ 行一个正整数代表 yyf 每次抽卡的欧气之和的最大值。

第 $2$ 行 $n$ 个正整数代表每次连抽的第一张卡的编号，如果有多种方案满足要求任意输出一种（如果不会输出方案也请在第二行随意输出 $n$ 个整数，否则可能 $0$ 分）。

方案请升序输出。

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

36
2 5 9

2 5 2 2
7 3 3 7 7 5 1 10 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\times (n+1) \ge m$。

共 $10$ 个测试点，每个测试点答案错误 $0$ 分，答案正确方案错误 $6$ 分，答案正确方案正确 $10$ 分。

样例解释：输出的方案就是样例解释了 QAQ。

样例一：单抽 $1$，连抽 $2\sim 4$，连抽 $5\sim 7$，单抽 $8$，连抽 $9\sim 11$，单抽 $12$，欧气值总和为 $2+7+5+8+5+9=36$。

样例二：单抽 $1$，连抽 $2\sim 3$，单抽 $4$，单抽 $5$，连抽 $6\sim 7$，单抽 $8$，单抽 $9$，欧气值总和为 $7+3+7+7+5+10+2=41$。

可以证明在满足条件的情况下上述两种方案是欧气值总和最大的。