士兵序列

在喵国，你有一支由$n$名预备役士兵组成的部队，士兵编号从$1$到$n$。现在你需要将他们拆分成若干个特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为$i,i+1,\ldots,i+k$的序列

编号为$i$的士兵初始战斗力为$x_i$，一支特别行动队的初始战斗力$X$为队内士兵的初始战斗力之和，即$x=x_1+x_2+\ldots+x_k$。

通过你长期的观察，你总结出一个特别行动队的初始战斗力$X$将按经验公式修正为 $X^\prime= aX^2+bX+c$，其中$a,b,c$是已知的系数。（$X^\prime$表示修正后的战斗力）

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

例如，你现在有4个士兵，战斗力分别为2，2，3，4。经验公式中的参数为$a=-1,b=10,c=-20$。此时的最佳方案是将士兵组成3个特别行动队：第一队包含士兵1和士兵2，第二队包含士兵3，第三队包含士兵4。特别行动队的初始战斗力分别为4，3，4，修正后的战斗力分别为4，1，4。修正后的战斗力之和为9，没有其他方案能使修正后的战斗力之和更大。

输入格式

第一行包括一个整数$n$，表示士兵的总数。

第二行包括三个整数$a, b, c$是经验公式中各项的系数。

第三行包含$n$个整数，$x_1, x_2,\ldots,x_n$，分别表示编号为$1,2,\ldots,n$的士兵的初始战斗力。

输出格式

输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。

提示

对于$20\%$的数据，有$1 \le n \le 1000$

对于$50\%$的数据，有$1 \le n \le 10000$

对于$100\%$的数据，有$1 \le n \le 1000000$

对于所有数据，有$-5 \le a \le -1, |b|\le 10^7,|c| \le 10^7,1 \le x_i \le 100$