Algorithm


A. Sockets
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 ai 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.

Input

The first line contains three integers nmk (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 a1, a2, ..., an (1 ≤ ai ≤ 50) — number ai stands for the number of sockets on the i-th supply-line filter.

Output

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.

Examples
input
Copy
3 5 3
3 1 2
output
Copy
1
input
Copy
4 7 2
3 3 2 4
output
Copy
2
input
Copy
5 5 1
1 3 1 2 1
output
Copy
-1
Note

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.

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.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <algorithm>

using namespace std;

int arr[51];

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    for(int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + 51);
    reverse(arr, arr + 51);
    
    int plugs = 0;
    
    for(int i = 0; k < m && i < n; i++) {
        plugs++;
        k += arr[i] - 1;
    }
    
    if(k >= m)
        cout << plugs << endl;
    else
        cout << -1 << endl;
  
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 5 3
3 1 2

Output

x
+
cmd
1
Advertisements

Demonstration


Codeforces Solution-Sockets-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+