时间限制：2000ms　内存限制：512MB

题目描述

粮站的仓库按月度盘点，程老师负责制定分垛方案。库里存着 $n$ 批粮食，按入库先后排成一队，第 $i$ 批重 $a_i$ 吨。盘点要求把这队粮食切成若干连续段，每段单独码放一个垛位，段与段之间不得交叉、不得调换顺序——先入库的必须在前面的垛位。这条规矩是粮站几十年的老传统，为的是先进先出、陈粮先销，盘点时顺着垛位走一圈，粮食的新旧一目了然。

垛位的管理费有两笔。一笔是按重量算的：一个垛位存了 $x$ 吨粮食，地坪承重维护费是 $x^2$ 元——重垛对地坪的损伤随重量平方上涨，这是工程科测出来的。另一笔是按垛位数算的：每启用一个垛位，固定收 $C$ 元的清扫消毒费。一个垛位的总费用就是这两笔之和。整个方案的总费用是所有垛位费用加起来。

码放规则还要交代几条。第一，每批粮食必须完整地编入某一段，中途不得拆批——批次之间隔着防潮隔板，拆批就乱了账。第二，空批也是批：个别批次的重量是 $0$ 吨（粮食已调出、批次档案还在），它照样要编入某一段，只是不给该段增重。第三，段数至少一段、至多 $n$ 段，每段至少含一批，不允许出现空段。第四，费用的计算只与各段的存粮总重和段数有关，与段内有几批、批次先后无关。

再举一笔账把两笔费用演一遍。设某段内有四批粮食，各重 $1, 2, 3, 4$ 吨，这一段存粮 $10$ 吨，地坪费 $10^2 = 100$ 元，加上固定费 $C$，才是这一段的总费用；若把这四批劈成两段，前段 $1, 2$ 共 $3$ 吨、后段 $3, 4$ 共 $7$ 吨，地坪费变成 $9 + 49 = 58$ 元，固定费却从一个 $C$ 变成两个 $C$。劈与不劈哪个划算，要两笔合起来比。工程科每年还要复核一次平方收费的费率表，费率表不动，只是重新确认地坪状况，确认完盖个章，计费方式照旧。

垛位数不是随意的。粮站的上级对盘点格式有要求：分垛数量必须落在 $L$ 到 $R$ 之间（含两端），分得太少是"盘点不细"，分得太多是"浪费垛位"，都要打回。在 $L$ 到 $R$ 这个范围里具体分几段，由程老师自己定，目标只有一个：总费用最少。这条规定每年都有微调，上下限以当月下发的盘点通知为准，方案算完后还要把分段数一并记在封面上备查。

这里有两股劲在别。地坪费按各段存粮总重的平方收，固定费按垛位个数收，分几段、在哪里切，会同时改变这两笔账。方案之间的高下，单凭任何一笔都定不了，必须两笔合起来核算。

这笔账往年是会计股拿手算的。粮食批数少的时候，会计把几种分法列在算盘上一核，半小时能出结果；这几年库里批次越滚越多，上个月会计股核了两天，报上去的方案还被工程科挑出更省的，场面十分难看。站长因此把本月的分垛核算交了出去，要求只报一个数：按规则能算出的最少总费用，一分都不能差。程老师给你各批粮食的重量、垛位固定费 $C$、段数下限 $L$ 和上限 $R$，请算出最少的总费用。

输入格式

第一行四个整数 $n, C, L, R$，分别表示粮食批数、每垛位固定费、段数下限、段数上限。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示各批粮食的重量（吨）。

输出格式

输出一行一个整数，表示满足段数要求的最少总费用（元）。

数据范围

• 特殊性质 A：$L = R$。
• 对于全部数据，$1 \le L \le R \le n \le 10^5$，$0 \le C \le 10^{12}$，$0 \le a_i \le 10^6$。

样例

样例 1

输入：

5 2 1 3
1 2 3 4 5

输出：

83

解释：逐一核算几种分法。分 $1$ 段：总重 $15$，费用 $225 + 2 = 227$。分 $2$ 段最省的是 $\{1,2,3\}$ 与 $\{4,5\}$：$36 + 81 + 2 \times 2 = 121$。分 $3$ 段最省的是 $\{1,2,3\}$、$\{4\}$、$\{5\}$：$36 + 16 + 25 + 2 \times 3 = 83$。段数上限 $R = 3$ 不允许再分，所以最少是 $83$ 元。

样例 2

输入：

5 2 1 1
1 2 3 4 5

输出：

227

解释：段数被限定为恰好 $1$ 段，别无选择，总费用 $15^2 + 2 = 227$ 元。

样例 3

输入：

4 50 1 4
1 2 3 4

输出：

150

解释：固定费 $C = 50$ 很贵。分 $1$ 段：$100 + 50 = 150$。分 $2$ 段最省的是 $\{1,2\}$ 与 $\{3,4\}$：$9 + 49 + 100 = 158$。分更多段，固定费还要继续加，更不划算。最少是 $150$ 元，对应只分 $1$ 段——尽管规则允许分到 $4$ 段。