A128506.星光灯带

$Sherry$ 正在布置学校科技节的星光花径。

花径可以看成一排从 $1$ 到 $n$ 编号的位置，第 $i$ 个位置有一个星光值 $a_i$。星光值可能为正，也可能为负。

$Sherry$ 可以在花径上安装若干条星光灯带。每条灯带必须覆盖一段连续的位置，并且长度不能太短也不能太长。具体来说，每条灯带覆盖的区间 $[l,r]$ 必须满足：

$$L \le r-l+1 \le R$$

如果一条灯带覆盖了区间 $[l,r]$，那么它能带来的美观值为：

$$a_l+a_{l+1}+\cdots+a_r-C$$

其中 $C$ 表示安装一条灯带需要消耗的固定代价。

为了避免灯光互相干扰，任意两条灯带之间必须至少隔开一个没有被灯带覆盖的位置。也就是说，如果一条灯带覆盖 $[l_1,r_1]$，另一条灯带覆盖 $[l_2,r_2]$，且 $r_1<l_2$，那么必须满足：

$$r_1+1<l_2$$

$Sherry$ 可以选择不安装任何灯带，此时总美观值为 $0$。

现在，请你帮 $Sherry$ 计算，最多可以获得多少总美观值。

第一行输入四个整数 $n,L,R,C$，分别表示花径长度、灯带最短长度、灯带最长长度和每条灯带的安装代价。

第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每个位置的星光值。

输出一个整数，表示最多可以获得的总美观值。

样例解释1

可以选择安装两条灯带：

• 第一条覆盖位置 $3\sim4$，美观值为 $6+2-3=5$。
• 第二条覆盖位置 $6\sim8$，美观值为 $5-2+3-3=3$。

两条灯带之间隔着位置 $5$，满足要求。

总美观值为：

$5+3=8$

---

样例解释2

所有位置的星光值都是负数，因此不安装任何灯带最优。

---

样例解释3

每条灯带只能覆盖一个位置，并且任意两条灯带之间必须至少隔开一个空位置。

可以选择位置 $1,3,5$，总美观值为：

$5+5+5=15$

---

数据范围

$1\le n\le 2\times 10^5$

$1\le L\le R\le n$

$0\le C\le 10^9$

$-10^9\le a_i\le 10^9$

答案可能较大，请使用 long long。