특공대

$1$번부터 $n$번까지 번호가 붙은 $n$명의 병사로 이루어진 군대를 이끄는 지휘관이 있다. 지휘관은 앞으로의 전투를 위해 $n$명의 병사를 여러 개의 특공대로 나누려고 한다. 결속력과 사기를 높이기 위해, 각 특공대는 번호가 연속하는 병사들, 즉 $\{i, i+1, \dots, j\}$ 형태로 구성되어야 한다.

각 병사 $i$의 전투력은 $x_i$이다. 특공대 $\{i, i+1, \dots, j\}$의 원래 전투력은 그 병사들의 전투력의 합, 즉 $x = x_i + x_{i+1} + \dots + x_j$였다.

그러나 여러 해에 걸친 영광스러운 승리 끝에, 특공대의 전투력을 다음과 같이 조정하기로 하였다. 특공대의 조정된 전투력 $x'$는 $x' = a x^2 + b x + c$ 로 계산한다. 여기서 $a$, $b$, $c$는 알려진 계수이고 $a < 0$이며, $x$는 위에서 정의한 특공대의 원래 전투력이다.

여러분이 할 일은 모든 특공대의 조정된 전투력의 합이 최대가 되도록 병사들을 특공대로 나누는 것이다.

입력은 세 줄로 이루어진다. 첫째 줄에는 병사의 수를 나타내는 양의 정수 $n$이 주어진다. 둘째 줄에는 조정된 전투력 공식의 계수인 세 정수 $a$, $b$, $c$가 주어진다. 셋째 줄에는 병사 $1, 2, \dots, n$의 전투력을 나타내는 $n$개의 정수 $x_1, x_2, \dots, x_n$이 공백으로 구분되어 주어진다.

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

얻을 수 있는 최대의 조정된 전체 전투력을 정수 하나로 출력한다.