В автобусе сидят $$$n$$$ пассажиров. Автобус застрял в снегу, и теперь им нужно вытолкнуть его оттуда.
Каждый пассажир имеет массу $$$m_i$$$ и силу $$$f_i$$$. Масса пустого автобуса равна $$$w$$$.
Часть пассажиров должна выйти из автобуса и начать толкать его, в то время как все остальные останутся внутри. Автобус можно будет вытолкнуть только в том случае, если суммарная сила толкающих будет больше либо равна суммарной массе автобуса с пассажирами, сидящими внутри.
Так как на улице довольно холодно, требуется минимизировать количество людей, которым нужно будет выйти из автобуса.
Выведите минимальное количество пассажиров, необходимое для того, чтобы вытащить автобус из снега. Если это невозможно, выведите $$$-1$$$.
Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целые числа $$$n$$$ и $$$w$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le w \le 10^9$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$m_1, m_2, m_3, \dots, m_n$$$ ($$$1 \le m_i \le 10^9$$$).
Третья строка содержит $$$n$$$ целых чисел $$$f_1, f_2, f_3, \dots, f_n$$$ ($$$1 \le f_i \le 10^9$$$).
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите единственное число — минимальное количество людей, необходимое для того, чтобы вытащить автобус из снега. Если это невозможно, выведите $$$-1$$$.
43 41 1 16 6 63 41 1 13 3 31 1000100106 107 5 1 4 2 83 1 2 7 5 9
1 2 -1 3
| TheForces Round #26 (Readall-Forces) |
|---|
| Закончено |
