题目描述

一家投资企业准备调整黄金买卖方案，以尽量增加最终利润。企业已经掌握一段时期的逐日报价，可以选择某日购入黄金，并在之后的日期将其出售，通过价差赚取收益。该时期内允许反复买卖，不过每轮交易都有手续费，起始本金也有上限。另外，每次购入的黄金数量相同，完整交易的总轮数不得突破规定额度。

任务：

根据每日报价、起始本金、每轮手续费以及可用交易额度，求出能够实现的最高净利润。

注意：

1. 一轮交易必须先购入，再于更晚的日期出售。
2. 整个时期内可安排多轮交易，但各轮不得重叠。尚有黄金未售出时，不能再次购入；出售时必须将当前持仓全部清空。
3. 每轮由一次购入和一次出售构成，仅在出售时收取一份手续费，且这笔费用与黄金数量无关。
4. 此前获利可以补充后续本金。执行购入时，可用现金必须不小于该批黄金的总价，否则该次购入不合法。可以选择全程不交易，最终只统计已经完成买卖的净利润。

输入描述

1. 首行给出整数 $N$，代表已知报价的天数，$2 \le N \le 500$。
2. 次行给出 $N$ 个以空格分隔的整数 $a_1,a_2,\ldots,a_N$，按日期顺序表示黄金单价，$1 \le a_i \le 1000$。
3. 第三行给出整数 $F$，代表完成一轮买卖所收取的费用，$0 < F \le 1000$。
4. 第四行给出整数 $C$，代表最初可用的现金，$0 < C \le 10000$。
5. 第五行给出整数 $K$，代表允许完成的买卖轮数上限，$0 < K \le 100$。
6. 第六行给出整数 $Q$，代表每次必须购入的黄金单位数，$1 \le Q \le 30$。

输出描述

输出一个整数，表示最优方案的净利润，即最终空仓时的现金减去起始本金。若所有可行交易均不能带来正利润，则输出 $0$。

样例 1

输入：

5
8 6 9 3 11
2
12
1
3

输出：

22

解释：

在第 $4$ 天购入 $3$ 单位黄金，需支付 $3 \times 3=9$，本金 $12$ 足够覆盖费用。

第 $5$ 天全部售出，收到 $11 \times 3=33$，再扣除手续费 $2$，这一轮净赚 $33-9-2=22$。

因此最高利润为 $22$。

整个方案仅完成 $1$ 轮买卖，符合额度要求。

样例 2

输入：

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

输出：

14

解释：

第 $2$ 天购入 $2$ 单位，支付 $2 \times 2=4$，恰好用完本金。

第 $4$ 天售出，扣费后得到 $7 \times 2-3=11$，这一轮赚得 $7$，可用现金变为 $11$。

第 $5$ 天再购入 $2$ 单位，需付 $4 \times 2=8$，此时已有现金足以支持。第 $6$ 天清仓，该轮利润为 $9 \times 2-8-3=7$。

两轮累计利润为 $7+7=14$。