Commando

A commander leads an army of $n$ soldiers numbered from $1$ to $n$. For the coming battles the commander wants to split the $n$ soldiers into several commando units. To build cohesion and morale, each unit must consist of soldiers with consecutive numbers, that is, of the form $\{i, i+1, \dots, j\}$.

Each soldier $i$ has combat power $x_i$. The raw combat power of a unit $\{i, i+1, \dots, j\}$ was originally the sum of its soldiers' powers, $x = x_i + x_{i+1} + \dots + x_j$.

After many glorious victories, however, the army decided to adjust a unit's combat power as follows: the adjusted combat power $x'$ of a unit is $x' = a x^2 + b x + c,$ where $a$, $b$, $c$ are known coefficients with $a < 0$, and $x$ is the unit's raw combat power defined above.

Your task is to split the soldiers into commando units so that the sum of the adjusted combat powers of all units is as large as possible.

The input consists of three lines. The first line contains a positive integer $n$, the number of soldiers. The second line contains three integers $a$, $b$, $c$, the coefficients of the adjusted-power formula. The third line contains $n$ integers $x_1, x_2, \dots, x_n$, separated by spaces, the combat powers of soldiers $1, 2, \dots, n$.

$n \le 1000000$, $-5 \le a \le -1$, $|b| \le 10000000$, $|c| \le 30000000$, $1 \le x_i \le 100$.

Print a single integer: the maximum total adjusted combat power that can be achieved.