Score Distribution Optimization

After the final exam, the class teacher, Mr./Ms. L, needs to distribute score sheets to all students. There are n score sheets, numbered from 1 to n and arranged in order on a table. The score on the i-th sheet is W_i.

The sheets are distributed in batches. For each batch, the teacher selects a contiguous segment from the current pile, and the students corresponding to those sheets pick up their scores. After that batch, the teacher repeats the process using the remaining sheets. After a number of batches, all sheets are distributed.

However, there are two considerations when planning the distribution:

• The psychological comfort of students – students in the same batch should not have scores that differ too much.
• The time cost – the number of batches should be minimized.

For a distribution plan, the cost is defined as \[ a \times k + b \times \sum_{i=1}^{k} (\max_i - \min_i)^2 \] where k is the number of batches, and for the i-th batch, \(\max_i\) and \(\min_i\) are the maximum and minimum scores in that batch, respectively. The parameters a and b are given.

Your task is to help teacher L find a distribution plan with the minimum total cost and output that minimum cost. You are free to choose the number of batches k.

inputFormat

The first line contains three integers: n (the number of score sheets), a, and b.

The second line contains n integers: W₁, W₂, \ldots, W_n, where W_i is the score on the i-th sheet.

outputFormat

Output a single integer, the minimum cost to distribute all the score sheets.

sample

5 10 1
10 20 30 20 10

50