Description

Original Source: APIO 2010

You have a troop of $n$ reserve soldiers, each numbered from $1$ to $n$, and you need to split them into several special action teams to deploy into the battlefield. For the sake of synergy, the soldiers in the same special action team should have consecutive numbers, forming a sequence like $(i, i + 1, \dots, i + k)$. The initial combat power of soldier $i$ is $x_i$, and the initial combat power $x$ of a special action team is the sum of the initial combat powers of its members, i.e., $x = x_i + x_{i+1} + \dots + x_{i+k}$. Through long-term observation, you have derived an empirical formula that adjusts the initial combat power $x$ of a special action team to $x'$ as follows: $x'= ax^2 + bx + c$, where $a, b, c$ are known coefficients ($a < 0$). As the commander, your task is to organize the troop into teams such that the sum of the adjusted combat powers of all special action teams is maximized. Determine this maximum sum. For example, suppose you have 4 soldiers with $x_1 = 2$, $x_2 = 2$, $x_3 = 3$, and $x_4 = 4$. The coefficients in the empirical formula are $a = –1$, $b = 10$, and $c = –20$. The optimal strategy is to form 3 special action teams: the first team includes soldiers $1$ and $2$, the second team includes soldier $3$, and the third team includes soldier $4$. The initial combat powers of the teams are $4$, $3$, and $4$, respectively, and their adjusted combat powers are $4$, $1$, and $4$. The total adjusted combat power is $9$, and no other grouping yields a larger sum.

Input Format

The input consists of three lines. The first line contains an integer $n$, the total number of soldiers. The second line contains three integers $a, b, c$, the coefficients in the empirical formula. The third line contains $n$ space-separated integers $x_1, x_2, \dots, x_n$, representing the initial combat powers of soldiers numbered $1, 2, \dots, n$.

Output Format

Output an integer representing the maximum possible sum of the adjusted combat powers of all special action teams.

Sample 1

4
-1 10 -20
2 2 3 4

9

Constraints and Hints

$20\%$ of the data satisfies $n \le 1000$; $50\%$ of the data satisfies $n \le 10^4$; $100\%$ of the data satisfies $1 \le n \le 10^6$, $-5 \le a \le -1$, $|b|, |c| \le 10^7$, and $1 \le x_i \le 100$.