该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

大样例下载

题目描述

Farmer John 的 $N$ 头奶牛排成一排，左数第 $i$ 头牛的身高为 $H_i$。

现在 John 要将奶牛分成若干组，他的分组是这样进行的：

首先，从队伍中选取连续的若干头奶牛作为第 $1$ 组并出队。

剩余的奶牛会靠拢在一起，相对位置不变。

再从队伍中选取连续的若干头奶牛作为第 $2$ 组并出队。

剩余的奶牛会靠拢在一起，相对位置不变。

依次类推，直到最后剩余的奶牛作为一组出队。

John 希望分在同一组的奶牛的“参差度”不要太大，即身高差距不要太大。对于第 $i$ 组奶牛，记该组中最高的奶牛身高为 $U_i$，最矮的奶牛身高为 $D_i$，John 定义该组奶牛的“参差度”为其“极差方”，记为 $R_i$，则 $R_i=(U_i-D_i)^2$。

同时，John 又希望分成的组数（记为 $M$）不要太多。为此，他制定了一个标准，记标准值 $S = C_1 × M + C_2 × \sum_{i=1}^M R_i$，其中 $C_1, C_2$ 为两个指定的整数，$\sum_{i=1}^M R_i$ 表示对所有组奶牛的“参差度”$R_i$求和，而 $M$ 的值也就是分成多少组则由 John 自行决定。分组完成后，根据以上式子计算出来的标准值 $S$ 越小，John 认为分组越合理。

问：John 将奶牛分成多少组，以及如何分组，可以使得 $S$ 尽可能小？你只需要输出可以得到的 $S$ 的最小值。

输入格式

第一行：一个正整数 $N$

第二行：两个整数 $C_1, C_2$

第三行：$N$ 个正整数 $H_i$

输出格式

一个整数，表示答案。

样例输入

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

输出

15

数据范围

100% 的数据：$N ≤ 50; 0 ≤ C_1 ≤ 1500; 0 ≤ C_2 ≤ 10; H_i ≤ 1000$