The final exams are over, and the class teacher, Teacher L, needs to distribute the transcripts to each student. Teacher L has a total of $n$ transcripts, stacked on the table in order from $1$ to $n$, where the score of the $i$-th transcript is $w_i$.

Transcripts are distributed in batches. When distributing, Teacher L takes a contiguous segment from the current stack of transcripts for a group of students to collect. After this group has finished collecting their transcripts, Teacher L takes another contiguous segment from the remaining transcripts for the next group. After several batches, all transcripts will have been distributed to the students.

However, distributing transcripts is a headache. On one hand, one must consider the students' feelings and avoid having students with vastly different scores collect their transcripts in the same batch; on the other hand, one must consider the time cost and minimize the number of batches. For a distribution scheme, we define its cost as:

$$a \times k + b \times \sum_{i=1}^{k} (\max_i - \min_i)^2$$

Where $k$ is the number of batches in the scheme, and for the $i$-th batch, $\max_i$ is the maximum score and $\min_i$ is the minimum score. $a$ and $b$ are given evaluation parameters.

Now, please help Teacher L find the distribution scheme with the minimum cost and tell Teacher L what this minimum cost is. Of course, the number of batches $k$ is determined by you.

Input

The first line contains a positive integer $n$, representing the number of transcripts. The second line contains two non-negative integers $a, b$, representing the given evaluation parameters. The third line contains $n$ positive integers $w_i$, representing the scores on the $i$-th transcript.

Output

A single integer representing the minimum cost.

Data Scale and Constraints

For all test cases, $1 \le n \le 100$, $0 \le a, b \le 10^9$, and $1 \le w_i \le 10^9$.

Examples

Input 1

10
3 1
7 10 9 10 6 7 10 7 1 2

Output 1

15

Note

Batch 1: Transcripts 2 to 4, difference is 1, remaining transcripts are 7 6 7 10 7 1 2; Batch 2: Transcript 4, difference is 0, remaining transcripts are 7 6 7 7 1 2; Batch 3: Transcripts 1 to 4, difference is 1, remaining transcripts are 1 2; Batch 4: The remaining 2 transcripts, difference is 1. Total cost is $4 \times 3 + (1^2 + 0^2 + 1^2 + 1^2) \times 1 = 15$.