Maximizing Modified Battle Power

You are given an army of n reservist soldiers numbered from 1 to n. You need to partition them into one or more special forces teams, where each team consists of consecutive soldiers (i.e. a segment of the form (i, i+1, …, i+k)). Every soldier must belong to exactly one team.

The initial combat power of soldier i is given by x_i. For any team covering soldiers with indices from i to i+k, the team’s initial combat power is

\(X = x_i + x_{i+1} + \cdots + x_{i+k}\).

Through long‐term observation, you have determined that the corrected combat power for a team with initial power \(X\) is calculated by the quadratic function

\(X' = aX^2 + bX + c\),

where a, b, and c are given coefficients with \(a < 0\). As the commander, your task is to split the soldiers into segments so that the sum of the corrected combat powers of all teams is maximized. Output the maximum total corrected combat power.

inputFormat

The input consists of three lines:

• The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of soldiers.
• The second line contains three integers a, b, and c (with \(a < 0\)); these are the coefficients in the corrected combat power function.
• The third line contains n integers \(x₁, x₂, \ldots, x_n\) representing the initial combat power of each soldier.

outputFormat

Output a single integer: the maximum total corrected combat power achievable by partitioning the soldiers into consecutive teams.

sample

5
-1 2 3
1 2 3 4 5

34