У вас есть рюкзак вместимостью $$$W$$$. У вас также есть $$$n$$$ предметов, вес $$$i$$$-го из них равен $$$w_i$$$.
Вы хотите поместить некоторые из этих предметов в рюкзак таким образом, чтобы их общий вес $$$C$$$ составлял как минимум половину его вместимости, но (очевидно) не превышал ее. Формально, $$$C$$$ должно удовлетворять: $$$\lceil \frac{W}{2}\rceil \le C \le W$$$.
Выведите список предметов, которые вы поместите в рюкзак, или определите, что удовлетворить условиям невозможно.
Если есть несколько возможных списков предметов, удовлетворяющих условиям, то можно вывести любой. Обратите внимание, что вы не должны максимизировать сумму весов элементов в рюкзаке.
Каждый тест содержит несколько наборов входных данных. В первой строке указано количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Описание наборов входных данных приведено ниже.
Первая строка каждого набора входных данных содержит целые числа $$$n$$$ и $$$W$$$ ($$$1 \le n \le 200\,000$$$, $$$1\le W \le 10^{18}$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 10^9$$$) — веса элементов.
Сумма $$$n$$$ по всем наборам входных данных не превышает $$$200\,000$$$.
Для каждого набора входных данных, если нет решения, выведите одно целое число $$$-1$$$.
Если есть решение, состоящее из $$$m$$$ предметов, выведите $$$m$$$ в первой строке и $$$m$$$ целых чисел $$$j_1$$$, $$$j_2$$$, ..., $$$j_m$$$ ($$$1 \le j_i \le n$$$, где все $$$j_i$$$ попарно различны) во второй строке — индексы предметов, которые вы хотели бы упаковать в рюкзак.
Если есть несколько возможных списков предметов, удовлетворяющих условиям, то можно вывести любой. Обратите внимание, что вы не должны максимизировать сумму весов элементов в рюкзаке.
3 1 3 3 6 2 19 8 19 69 9 4 7 12 1 1 1 17 1 1 1
1 1 -1 6 1 2 3 5 6 7
В первом наборе входных данных, вы можете взять предмет весом $$$3$$$ и полностью заполнить рюкзак.
Во втором наборе входных данных, все предметы больше, чем рюкзак. Следовательно, ответ $$$-1$$$.
В третьем наборе входных данных вы заполните рюкзак ровно наполовину.
Название |
---|