#155. LCL 的取钱计划

LCL 的母亲为 LCL 的相亲准备了丰厚的资金，但是资金存在银行卡中无法取出。

当 LCL 有女朋友他才能拿到每天 $A$ 元的补贴。

由于 LCL 非常有钱，现在有 $k$ 个妹子看上了 LCL，但是 LCL 人品极差，每个妹子在于 LCL 相处 $X$ 天后一定会和 LCL 分手，当然 LCL 也可以随时选择甩了当前的女朋友。

然而 LCL 并不缺少洗钱的方法，每天他参加比赛时会先从银行卡中预支全部队伍的比赛费用，并且能够在比赛后拿到所有费用的报销。

注意如果 LCL 在有女朋友的时候外出比赛回和当前女友发生不可调和的矛盾，会导致这个妹子提前一天提出分手。

如果 LCL 连续 $Y$ 天有女朋友（注意可能是不同的女朋友），他就会因为成绩太差被禁止参加比赛。禁赛会一直持续到下一次单身的前一天（即单身的那一天可以参加比赛）。现在已知接下来 $n$ 天比赛的费用，请你帮助贪心的 LCL 获得最大的收益。

第一行仅有一个数字 $T(1\le T\le 3)$ 代表数据组数。下面依次是每一组数据

每组数据仅有一行两个整数 $n,K,A,X,Y(1\le n\le 1000,1\le K\le 5,1\le A,X\le 1000,1\le Y\le 5)$。

接下来 $1$ 行 $n$ 个数字，每个数字代表第 $i$ 个月 LCL 参加比赛可以洗出的钱 $a_i(0\le a_i\le 1000)$。

每组数据输出一行一个数字代表最大收益。

样例输入

2
4 1 500 2 5
953 27 89 853
5 2 500 3 4
1 1 1 1 10

样例输出

2806
2501