257A.md (2570B)
1 Source: https://codeforces.com/problemset/problem/257/A 2 3 A. Sockets 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 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. 24 25 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. 26 27 Input 28 29 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. 30 31 Output 32 33 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. 34 35 Examples 36 37 Input 38 39 ``` 40 3 5 3 41 3 1 2 42 ``` 43 44 Output 45 46 ``` 47 1 48 ``` 49 50 Input 51 52 ``` 53 4 7 2 54 3 3 2 4 55 ``` 56 57 Output 58 59 ``` 60 2 61 ``` 62 63 Input 64 65 ``` 66 5 5 1 67 1 3 1 2 1 68 ``` 69 70 Output 71 72 ``` 73 -1 74 ``` 75 76 Note 77 78 In the first test case he can plug the first supply-line filter directly to electricity. After he plug it, he get 5 (3 on the supply-line filter and 2 remaining sockets for direct plugging) available sockets to plug. Thus, one filter is enough to plug 5 devices. 79 80 One of the optimal ways in the second test sample is to plug the second supply-line filter directly and plug the fourth supply-line filter to one of the sockets in the second supply-line filter. Thus, he gets exactly 7 sockets, available to plug: one to plug to the electricity directly, 2 on the second supply-line filter, 4 on the fourth supply-line filter. There's no way he can plug 7 devices if he use one supply-line filter.