Codeforces Round 697 (Div. 3) |
---|
Закончено |
Поликарп часто пользуется своим смартфоном. Он уже установил на него $$$n$$$ приложений. Приложение с номером $$$i$$$ занимает $$$a_i$$$ единиц памяти.
Недавно Поликарпу потребовалось установить новое приложение на свой смартфон. Однако, для установки требуется освободить хотя бы $$$m$$$ единиц памяти (удаляя некоторые приложения).
Конечно же, некоторые приложения для Поликарпа важнее, чем другие. Он придумал следующую систему оценки — каждому приложению он сопоставил целое число $$$b_i$$$:
По такой системе оценки, его телефон имеет $$$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]$$$, то Поликарп может удалить следующие наборы приложений (ниже перечислены не все варианты):
Помогите Поликарпу, выберите набор приложений, удалив которые он освободит хотя бы $$$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$$$.
Для каждого набора входных данных в отдельной строке выведите:
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$$$.
Название |
---|