题目描述

你有一支由$\red {n}$名士兵组成的部队，士兵从$\red {1}$到$\red {n}$编号，要将他们拆分成若干个特别行动队调入战场。

出于默契的考虑，同一支行动队的队员的编号应该连续。

编号为$\red {i}$的士兵的初始战斗力为$\red {x_i}$，一支行动队的初始战斗力为队内所有队员初始战斗力之和。

通过长期观察，你总结出一支特别行动队的初始战斗力$\red {x}$将按如下公式修正为$\red {x’}$:

$\red {x′=ax ^2 +bx+c}$

其中，$\red {a,b,c}$是已知的系数$\red {(a<0)}$。

作为部队统帅，你要为这支部队进行编队，使得所有特别行动队修正后的战斗力之和最大。

试求出这个最大和。

输入格式

第一行包含一个整数$\red {n}$，表示士兵总数。

第二行包含三个整数$\red {a,b,c}$。

第三行包含$\red {n}$个整数$\red {x _1 ,x_2 ,…,x_n}$,表示每名士兵的初始战斗力。

输出格式

输出一个整数，表示战斗力之和的最大值。

样例

输入样例

4 
-1 10 -20 
2 2 3 4

输出样例

9

提示

$\red {1≤n≤1000000}$,

$\red {−5≤a≤−1}$,

$\red {|b|,|c|≤10^7}$,

$\red {1≤x _i ≤100}$