← 返回题目列表

Codeforces · 611/E

E. 新年和三个火枪手

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

你知道三个火枪手的故事吗?无论如何,你现在必须帮助他们。

Richelimakieu 是贝尔里斯市的一位红衣主教。他找到了三位勇敢的战士,并称他们为“三剑客”。阿托斯的力量为a,博尔托斯的力量为b,卡拉米斯的力量为c。

2015年已经快过去了,还有n个罪犯有待击败。第 i 个罪犯的力量为 ti。打败强大的罪犯是很困难的——也许火枪手必须共同战斗才能实现这一目标。

Richelimakieu 将协调火枪手的行动。在每一小时内,每个火枪手要么什么也不做,要么被指派去对付一名罪犯。可以将两个或三个火枪手分配给同一个罪犯,然后总结他们的优势。一个罪犯可以在一小时内被击败(即使有两三个火枪手与他战斗)。黎塞利马基厄不能允许罪犯的力量比与他战斗的火枪手的力量总和还要大——那样罪犯就会获胜!

换句话说,打败罪犯有三种方法。

- 力量x的火枪手在一小时内可以击败力量不大于x的罪犯。因此,例如,只有当 ti ≤ a 时,Athos 才能在一小时内击败罪犯 i。
- 两个火枪手可以并肩作战,并在一小时内击败一名实力不大于这两个火枪手力量总和的罪犯。因此,例如,只有当 ti ≤ a + c 时,Athos 和 Caramis 才能在一小时内击败罪犯 i。请注意,剩下的第三个火枪手要么什么也不做,要么与其他罪犯战斗。
- 同样,三个火枪手可以一起战斗,并在一小时内击败一个力量不大于火枪手力量总和的罪犯,即ti ≤ a + b + c。

Richelimakieu 不希望火枪手在除夕夜打仗。因此,他必须协调他们的行动,以尽量减少击败所有罪犯的时间。

找出击败所有罪犯的最少小时数。如果火枪手无法击败他们,则打印“-1”(不带引号)。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 罪犯的数量。

第二行包含三个整数 a、b 和 c (1 ≤ a, b, c ≤ 108) — 火枪手的实力。

第三行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 108) – 犯罪分子的强度。

输出

打印一行答案。

如果不可能击败所有罪犯,请打印“-1”(不带引号)。否则,打印三个火枪手击败所有罪犯所需的最少小时数。

示例

输入 #1

5
10 20 30
1 1 1 1 50

输出 #1

2

输入 #2

5
10 20 30
1 1 1 1 51

输出 #2

3

输入 #3

7
30 20 10
34 19 50 33 88 15 20

输出 #3

-1

输入#4

6
10 5 10
10 9 5 25 20 5

输出#4

3

注意

在第一个样本中,Athos 的力量为 10,Borthos 为 20,Caramis 为 30。他们可以在两小时内击败所有罪犯:

- 博尔托斯和卡拉米斯应该一起对抗力量为 50 的罪犯。在同一小时内,阿托斯可以对抗力量为 1 的四个罪犯之一。
- 还剩下三名罪犯,每人力量为1。每个火枪手在第二小时内可以与一名罪犯战斗。

在第二个样本中,所有三个火枪手必须一起对抗力量为 51 的罪犯。需要一小时。在第二个小时里,他们可以单独战斗,每人对付一名罪犯。第三小时内只剩下一名罪犯,任何火枪手都可以与他战斗。