Description

You command a unit consisting of $n$ reserve soldiers, numbered from $1$ to $n$. You need to split them into several commando teams to be deployed to the battlefield. For teamwork reasons, the indices of the members within the same commando team must be consecutive, i.e., a sequence of the form $(i, i + 1, \cdots,i + k)$. Every soldier must belong to exactly one commando team.

The initial combat power of soldier $i$ is $x_i$. The initial combat power $X$ of a commando team is the sum of the initial combat power of its members, i.e., $X = x_i + x_{i+1} + \cdots + x_{i+k}$.

From long-term observation, you have summarized that for a commando team with initial combat power $X$, its adjusted combat power is $X' = aX^2 + bX + c$, where $a, b, c$ are known coefficients ($a < 0$). As the commander, you must form the teams so that the sum of adjusted combat power over all commando teams is maximized. Find this maximum sum.

Input Format

The first line contains an integer $n$, the number of soldiers.

The second line contains three space-separated integers, $a, b, c$, which are the coefficients of the adjusted combat power formula.

The third line contains $n$ space-separated integers, where the $i$-th integer is the initial combat power $x_i$ of soldier $i$.

Output Format

Output a single integer on one line, the maximum possible sum of adjusted combat power over all commando teams.

4 
-1 10 -20 
2 2 3 4 

9

Hint

Explanation of Sample Input/Output 1

You have $4$ soldiers, $x_1 = 2,~x_2 = 2,~x_3 = 3,~x_4 = 4$. The parameters in the adjusted combat power formula are $a = -1,~b = 10,~c = -20$.

The optimal plan is to form $3$ commando teams: the first team contains soldiers $1$ and $2$, the second team contains soldier $3$, and the third team contains soldier $4$. The initial combat powers of the teams are $4,~3,~4$, and the adjusted combat powers are $-4^2 + 10 \times 4 - 20 = 4$, $-3^2 + 10 \times 3 - 20 = 1$, $-4^2 + 10 \times 4 - 20 = 4$. The sum of adjusted combat powers is $4 + 1 + 4 = 9$, and no other plan yields a larger sum.

Constraints

For $20\%$ of the testdata, $n \leq 10^3$.

For $50\%$ of the testdata, $n \leq 10^4$.

For $100\%$ of the testdata, $1 \leq n \leq 10^6$, $-5 \leq a \leq -1$, $-10^7 \leq b \leq 10^7$, $-10^7 \leq c \leq 10^7$, $1 \leq x_i \leq 100$.

Translated by ChatGPT 5