1부터 n 까지 번호가 붙여진 n 명의 병사들로 이루어진 군대의 지휘관이 있다.

이 지휘관은 앞으로의 전투를 위하여 n 명의 병사들을 여러 개의 특공대로 나누고자 한다. 결속력과 사기 를 높이기 위하여 각 특공대는 {i, i+1 , i+2 , .. , i+k}飴凰쩜번호가 연속하는 병사들로 구성된다.

각 병사 i의 전투력은 xi이다. 병사들 i, i+1 , i+2 , .. , i+k}로 구성된 특공대의 전투력 x 는 원 래는 각 병사의 전투력의 합으로 계산되었다. 달리 말하면 x = xi + xi+1 + ..+ xi+k 이었다.

그러나 여러 해의 영광스러운 승리를 통하여 특공대의 전투력을 다음과 같이 조정해야 하 는 것으로 결론을 내렸다: 특공대의 조정된 전투력 x′는 등식 ax^2 + bx + c로 계산한다. 여기서 a,b,c는 알려져 있는 계수들로서 a < 0 이고, x 는 특공대의 원래 정의된 전투력이다.

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

예를 들어, 4명의 병사들이 있고, 각 병사의 전투력 x1 = 2 , x2 = 3 , x3 = 3 , x4 = 4 라 하자.

특공대의 조정된 전투력 등식에 있는 계수가 a = -1 , b = 10 , c = -20 이라 하자. 이러한 경우, 최적인 해는 병사들을 다음과 같이 세 개의 특공대로 나누는 것이다:

• 첫 번째 특공대는 병사 1과 2로 구성하고,
• 두 번째 특공대는 병사 3으로 구성하고,
• 세 번째 특공대는 병사 4로 구성한다.

입력

• 첫 번째 줄에 전체 병사들 수인 양의 정수 n 이 주어진다.
• 두 번 째 줄에 특공대의 조정된 전투력 계산 등식의 계수인 세 정수 a,b,c가 주어진다.
• 마지막 줄 에 병사들 1,2,3,..,n 의 전투력을 나타내는 n 개의 정수 x1,x2,...,xn 이 공백을 사이에 두고 주어진다.

출력

입출력 예

입력

4 
-1 10 -20
2 2 3 4

출력

9

제약조건

• 테스트 경우의 20%가 n ≤ 1000
• 테스트 경우의 50%가 n ≤ 10,000
• 테스트 경우의 100%가 n ≤ 1,000,000 , -5 ≤ a ≤1 |b| ≤ 0,000,000 , c| ≤ 10,000,000, 1 ≤ xi ≤ 100 이다.

출처: Asia-Pacific Informatics Olympiad 2010