У Максима есть
n книг различных жанров. В
i-й книге
ai страниц. Сегодня он хочет прочитать не менее
xj страниц, при этом, чтобы не запутаться в историях, он хочет прочитать как можно меньше книг.
Помогите Максиму определить минимальное количество книг, которые он должен прочитать, чтобы общее число прочитанных страниц было не менее
xj. Если это невозможно, выведите
-1. Максим не может читать одну и ту же книгу дважды.
Формат входных данных
Первая строка содержит натуральное число n (1 ≤ 𝑛 ≤ 105) - количество книг, которые есть у Максима. Вторая строка содержит n целых чисел a1, a2, ..., an (1≤ ai ≤104) - количество страниц в i-й книге. Третья строка содержит натуральное число xj (1 ≤ xj ≤ 2⋅109) - количество страниц, которое хочет прочитать Максим.
Формат выходных данных
Выведите ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 7 2 9 4
12
|
2
|