301371: CF257A. Sockets
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Sockets
题意翻译
Vasya 有 $m$ 个电器需要用电, 他有 $n$ 个插线板, 第 $i$ 个插线板有 $a_i$ 个插口, 每个插口可以插入另一个插线板或一个电器 他的公寓一共有 $k$ 个插座, 每个插座可以插入一个插线板或一个电器, 求他最少需要多少个插线板, 才可以让所有电器都通电。 若无论如何都无法让所有电器通电, 就输出 $-1$ 。题目描述
Vasya has got many devices that work on electricity. He's got $ n $ supply-line filters to plug the devices, the $ i $ -th supply-line filter has $ a_{i} $ sockets. Overall Vasya has got $ m $ devices and $ k $ electrical sockets in his flat, he can plug the devices or supply-line filters directly. Of course, he can plug the supply-line filter to any other supply-line filter. The device (or the supply-line filter) is considered plugged to electricity if it is either plugged to one of $ k $ electrical sockets, or if it is plugged to some supply-line filter that is in turn plugged to electricity. What minimum number of supply-line filters from the given set will Vasya need to plug all the devices he has to electricity? Note that all devices and supply-line filters take one socket for plugging and that he can use one socket to plug either one device or one supply-line filter.输入输出格式
输入格式
The first line contains three integers $ n $ , $ m $ , $ k $ ( $ 1<=n,m,k<=50 $ ) — the number of supply-line filters, the number of devices and the number of sockets that he can plug to directly, correspondingly. The second line contains $ n $ space-separated integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=50 $ ) — number $ a_{i} $ stands for the number of sockets on the $ i $ -th supply-line filter.
输出格式
Print a single number — the minimum number of supply-line filters that is needed to plug all the devices to electricity. If it is impossible to plug all the devices even using all the supply-line filters, print -1.
输入输出样例
输入样例 #1
3 5 3
3 1 2
输出样例 #1
1
输入样例 #2
4 7 2
3 3 2 4
输出样例 #2
2
输入样例 #3
5 5 1
1 3 1 2 1
输出样例 #3
-1