303139: CF611E. New Year and Three Musketeers
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
New Year and Three Musketeers
题意翻译
有 $n$ 个怪兽,每个怪兽有一个战斗力 $t_i$,有三个战士,战斗力分别为$a$,$b$,$c$ 每名战士在每个时刻可以选择与一个怪物战斗,多个战士可以同时选择同一只怪物进行战斗,对于一个怪物来说,当且仅当在某一个时刻同时与其战斗的战士战斗力之和大于等于其战斗力 $t$,这头怪物才会被消灭 求将所有怪物消灭所需要的最少时间 数据范围:$1\leq n\leq 200000$, $1\leq t_i,a,b,c\leq 10^8$。题目描述
Do you know the story about the three musketeers? Anyway, you must help them now. Richelimakieu is a cardinal in the city of Bearis. He found three brave warriors and called them the three musketeers. Athos has strength $ a $ , Borthos strength $ b $ , and Caramis has strength $ c $ . The year 2015 is almost over and there are still $ n $ criminals to be defeated. The $ i $ -th criminal has strength $ t_{i} $ . It's hard to defeat strong criminals — maybe musketeers will have to fight together to achieve it. Richelimakieu will coordinate musketeers' actions. In each hour each musketeer can either do nothing or be assigned to one criminal. Two or three musketeers can be assigned to the same criminal and then their strengths are summed up. A criminal can be defeated in exactly one hour (also if two or three musketeers fight him). Richelimakieu can't allow the situation where a criminal has strength bigger than the sum of strengths of musketeers fighting him — a criminal would win then! In other words, there are three ways to defeat a criminal. - A musketeer of the strength $ x $ in one hour can defeat a criminal of the strength not greater than $ x $ . So, for example Athos in one hour can defeat criminal $ i $ only if $ t_{i}<=a $ . - Two musketeers can fight together and in one hour defeat a criminal of the strength not greater than the sum of strengths of these two musketeers. So, for example Athos and Caramis in one hour can defeat criminal $ i $ only if $ t_{i}<=a+c $ . Note that the third remaining musketeer can either do nothing or fight some other criminal. - Similarly, all three musketeers can fight together and in one hour defeat a criminal of the strength not greater than the sum of musketeers' strengths, i.e. $ t_{i}<=a+b+c $ . Richelimakieu doesn't want musketeers to fight during the New Year's Eve. Thus, he must coordinate their actions in order to minimize the number of hours till all criminals will be defeated. Find the minimum number of hours to defeat all criminals. If musketeers can't defeat them all then print "-1" (without the quotes) instead.输入输出格式
输入格式
The first line of the input contains a single integer $ n $ ( $ 1<=n<=200000 $ ) — the number of criminals. The second line contains three integers $ a $ , $ b $ and $ c $ ( $ 1<=a,b,c<=10^{8} $ ) — strengths of musketeers. The third line contains $ n $ integers $ t_{1},t_{2},...,t_{n} $ ( $ 1<=t_{i}<=10^{8} $ ) — strengths of criminals.
输出格式
Print one line with the answer. If it's impossible to defeat all criminals, print "-1" (without the quotes). Otherwise, print the minimum number of hours the three musketeers will spend on defeating all criminals.
输入输出样例
输入样例 #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