A7450 | 星光灯带

$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$，表示每个位置的星光值。

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