UOJ Logo Zijian Online Judge

ZOJ

#7. 画心

统计

渠是一名画师。渠有一支神奇的画笔,可以画尽因果。

渠要画一幅画,这幅画由$N$个线段组成,线段从$1$开始编号,第$i$条线段有一个特殊的因果值$Ai$。

由于画太长了,渠不可能一次画完,于是渠打算将这$N$条线段分成若干组来画,每一组的长度要求在$[L,R]$之间,且必须是编号连续的一段。

对于因果值之和为$x$的一组线段,渠画完后种下的因果为$ax^2+bx+c$。渠想知道渠将这$N$条线段画完,最多收获多少因果呢?

输入格式

输入共三行。

第一行为$4$个整数$N$,$a$,$b$,$c$,表示线段的数目与给定的参数。

第二行为$2$个正整数$L$,$R$,为每组长度限制的区间。

第三行为$N$个整数$Ai$,分别表示每一条线段的因果值。

输出格式

仅一行,为最多收获的因果数,保证答案在long long范围之内。

样例

Input

7 -1 0 3
1 3
1 -2 3 -4 5 6 -6

Output

9

Explanation

第一次完成编号为$[2,3]$的一段,收获$2$因果。

第二次完成编号为$[4,5]$的一段,收获$2$因果。

第三次完成编号为$[1,1]$的一段,收获$2$因果。

第四次完成编号为$[6,7]$的一段,收获$3$因果。

共计$9$因果。

限制与约定

对于$20\texttt{%}$的数据 : $1 \leq N \leq 10$。

对于$40\texttt{%}$的数据 : $1 \leq N \leq 10^3$。

另有$20\texttt{%}$的数据 : $L=1$, $R=N$, $0 \leq Ai \leq 10^5$。

另有$20\texttt{%}$的数据 : $L=1$, $R=N$。

对于$100\texttt{%}$的数据 : $1 \leq N \leq 52501$, $0 \leq b,c \leq 52501$, $0 \leq |Ai| \leq 10^4$, $-10 < a < 0$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$