← 返回题目列表

Codeforces · 234/F

F. 栅栏

中文机器翻译题面 查看原题

Vasya 应该在他自己的小屋前画一道栅栏。栅栏是一系列排列成单行的 n 块木板。每块板都是一个 1 厘米宽的矩形。让我们从左到右使用数字 1、2、...、n 对板栅栏进行编号。第i块板的高度为hi厘米。

Vasya 有一支 1 厘米宽的画笔和两种颜色的颜料:红色和绿色。当然,涂料的用量是有限的。瓦夏计算了他可以绘制每种颜色的面积。原来,他不能把栅栏的一平方厘米涂成红色,也不能把b平方厘米涂成绿色。栅栏的每块板都应该涂上两种颜色中的一种。也许瓦夏不需要其中一种颜色。

此外,Vasya 希望他的栅栏看起来很漂亮。为此,他应该对栅栏进行油漆,以最小化 Vasya 所说的栅栏不美观值。瓦西亚认为,两块连续的栅栏板涂有不同的颜色,看起来没有吸引力。栅栏的不美观值是各种颜色的相邻板之间的接触总长度。为了使栅栏看起来漂亮,您需要将值最小化为尽可能低的值。你的任务是找出如果瓦夏完全粉刷他的栅栏的话,他能得到的最小的不吸引力是多少。

图为栅栏,其中木板的高度(从左到右)分别为2,3,2,4,3,1。第一块和第五块板漆成红色,其余板漆成绿色。第一块和第二块板的接触长度为2,第四块和第五块板的接触长度为3,第五块和第六块的接触长度为1。因此,给定的油漆栅栏的不美观度为2+3+1=6。

输入

第一行包含一个整数 n (1 ≤ n ≤ 200) — Vasya 围栏中的木板数量。

第二行包含两个整数a和b(0 ≤ a, b ≤ 4·104)——分别是可以涂成红色的区域和可以涂成绿色的区域。

第三行包含 n 个整数 h1, h2, ..., hn (1 ≤ hi ≤ 200) 的序列 — 栅栏板的高度。

行中的所有数字均以单个空格分隔。

输出

打印一个数字——如果 Vasya 完全粉刷他的栅栏,他可以获得的最小不吸引力值。如果不可能,则打印 - 1。

示例

输入 #1

4
5 7
3 3 4 1

输出 #1

3

输入 #2

3
2 3
1 3 1

输出 #2

2

输入 #3

3
3 3
2 2 2

输出 #3

-1