У вас есть рюкзак вместимостью \(W\). У вас также есть \(n\) предметов, вес \(i\)-го из них равен \(w_i\).
Вы хотите поместить некоторые из этих предметов в рюкзак таким образом, чтобы их общий вес \(C\) составлял как минимум половину его вместимости, но (очевидно) не превышал ее. Формально, \(C\) должно удовлетворять: \(\lceil \frac{W}{2}\rceil \le C \le W\).
Выведите список предметов, которые вы поместите в рюкзак, или определите, что удовлетворить условиям невозможно.
Если есть несколько возможных списков предметов, удовлетворяющих условиям, то можно вывести любой. Обратите внимание, что вы не должны максимизировать сумму весов элементов в рюкзаке.
Выходные данные
Для каждого набора входных данных, если нет решения, выведите одно целое число \(-1\).
Если есть решение, состоящее из \(m\) предметов, выведите \(m\) в первой строке и \(m\) целых чисел \(j_1\), \(j_2\), ..., \(j_m\) (\(1 \le j_i \le n\), где все \(j_i\) попарно различны) во второй строке — индексы предметов, которые вы хотели бы упаковать в рюкзак.
Если есть несколько возможных списков предметов, удовлетворяющих условиям, то можно вывести любой. Обратите внимание, что вы не должны максимизировать сумму весов элементов в рюкзаке.
Примечание
В первом наборе входных данных, вы можете взять предмет весом \(3\) и полностью заполнить рюкзак.
Во втором наборе входных данных, все предметы больше, чем рюкзак. Следовательно, ответ \(-1\).
В третьем наборе входных данных вы заполните рюкзак ровно наполовину.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|