D. Очистка телефона
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп часто пользуется своим смартфоном. Он уже установил на него $$$n$$$ приложений. Приложение с номером $$$i$$$ занимает $$$a_i$$$ единиц памяти.

Недавно Поликарпу потребовалось установить новое приложение на свой смартфон. Однако, для установки требуется освободить хотя бы $$$m$$$ единиц памяти (удаляя некоторые приложения).

Конечно же, некоторые приложения для Поликарпа важнее, чем другие. Он придумал следующую систему оценки — каждому приложению он сопоставил целое число $$$b_i$$$:

  • $$$b_i = 1$$$ — обычное приложение;
  • $$$b_i = 2$$$ — важное приложение.

По такой системе оценки, его телефон имеет $$$b_1 + b_2 + \ldots + b_n$$$ очков удобства.

Поликарп считает, что если он удалит приложения с номерами $$$i_1, i_2, \ldots, i_k$$$, то он освободит $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ единиц памяти и потеряет $$$b_{i_1} + b_{i_2} + \ldots + b_{i_k}$$$ очков удобства.

Например, если $$$n=5$$$, $$$m=7$$$, $$$a=[5, 3, 2, 1, 4]$$$, $$$b=[2, 1, 1, 2, 1]$$$, то Поликарп может удалить следующие наборы приложений (ниже перечислены не все варианты):

  • приложения с номерами $$$1, 4$$$ и $$$5$$$. В таком случае он освободит $$$a_1+a_4+a_5=10$$$ единиц памяти и потеряет $$$b_1+b_4+b_5=5$$$ очков удобства;
  • приложения с номерами $$$1$$$ и $$$3$$$. В таком случае он освободит $$$a_1+a_3=7$$$ единиц памяти и потеряет $$$b_1+b_3=3$$$ очков удобства.
  • приложения с номерами $$$2$$$ и $$$5$$$. В таком случае он освободит $$$a_2+a_5=7$$$ единиц памяти и потеряет $$$b_2+b_5=2$$$ очков удобства.

Помогите Поликарпу, выберите набор приложений, удалив которые он освободит хотя бы $$$m$$$ единиц памяти и потеряет минимальное количество очков удобства или укажите, что не существует такого набора.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — количество приложений на телефоне Поликарпа и количество единиц памяти, которые требуется освободить.

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — количество единиц памяти, занимаемое приложениями.

В третьей строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2$$$) — оценка каждого приложения по системе Поликарпа.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите:

  • -1, если не существует набора приложений, удаление которых освободит хотя бы $$$m$$$ единиц памяти;
  • минимальное количество очков удобства, которые Поликарп потеряет, если такой набор существует.
Пример
Входные данные
5
5 7
5 3 2 1 4
2 1 1 2 1
1 3
2
1
5 10
2 3 2 3 2
1 2 1 2 1
4 10
5 1 3 4
1 2 1 2
4 5
3 2 1 2
2 1 2 1
Выходные данные
2
-1
6
4
3
Примечание

В первом наборе входных данных оптимально удалить приложения с номерами $$$2$$$ и $$$5$$$, освободив $$$7$$$ единиц памяти. $$$b_2+b_5=2$$$.

Во втором наборе входных данных удалив единственное приложение Поликарп сможет очистить только $$$2$$$ единицы памяти из $$$3$$$ необходимых.

В третьем наборе входных данных оптимально удалить приложения с номерами $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$, освободив $$$10$$$ единиц памяти. $$$b_1+b_2+b_3+b_4=6$$$.

В четвертом наборе входных данных оптимально удалить приложения с номерами $$$1$$$, $$$3$$$ и $$$4$$$, освободив $$$12$$$ единиц памяти. $$$b_1+b_3+b_4=4$$$.

В пятом наборе входных данных оптимально удалить приложения с номерами $$$1$$$ и $$$2$$$, освободив $$$5$$$ единиц памяти. $$$b_1+b_2=3$$$.