Bob is working on his biology assignment! He has ~N~ plants in a row and needs to water all of them today. Bob wants to water the ~i^\text{th}~ plant with ~v_i~ milliliters of water. He can spray exactly ~1~ milliliter of water onto each plant in a contiguous row of length ~i~ at a cost of ~A \cdot i + B~ where ~A~ and ~B~ are given positive integers.

Bob is also okay with cutting some corners with his plant project. Specifically, say he ends up watering the ~i^\text{th}~ plant with ~w_i~ milliliters. Then he will consider ~C \cdot ((w_1-v_1)^2 + (w_2-v_2)^2 + \dots + (w_N-v_N)^2)~ as an additional cost, where ~C~ is some given positive integer.

Help Bob minimize the sum of these costs!

Constraints

For all subtasks:

~0 \le A, B, C \le 100~

~0 \le v_i \le 100~ for all ~1 \le i \le N~

Subtask 1 [40%]

~1 \le N \le 2\,000~

Subtask 2 [60%]

~1 \le N \le 200\,000~

Input Specification

The first line contains a single integer ~N~.
The next line contains three space-separated integers ~A, B, C~ in that order.
The final line contains ~N~ space-separated integers ~v_1, v_2, \dots, v_N~.

Output Specification

Output a single integer, the minimum possible sum of the costs.

Sample Input 1

5
1 9 8
1 1 0 1 1

Sample Output 1

22

Sample Input 2

8
1 2 100
2 2 0 1 0 1 1 1

Sample Output 2

16