L. Задача о прочном рюкзаке
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задача о рюкзаке — классическая задача информатики.

Её формулировка такова: есть $$$n$$$ предметов, для каждого из которых известны его вес $$$w_i$$$ и стоимость $$$cost_i$$$. Также задана грузоподъёмность рюкзака $$$W$$$  — ограничение на суммарный вес предметов, которые вы можете взять. Требуется выбрать несколько предметов с суммарным весом не более $$$W$$$ так, чтобы их суммарная стоимость была как можно больше.

В этой задаче вам не требуется решить классическую задачу о рюкзаке. Жюри уже решило её и нашло точный ответ: максимальная возможная суммарная стоимость предметов, влезающих в рюкзак грузоподъёмности $$$W$$$, равна $$$x$$$. Это число жюри вам не сообщает.

Ваша задача  — решить «задачу о прочном рюкзаке». Теперь рюкзак заявленной грузоподъёмности $$$W$$$ может выдержать вес до $$$\frac{3}{2}W$$$. Вам нужно решить задачу с ослабленным ограничением не хуже, чем жюри решило задачу с ограничением $$$W$$$.

Иными словами, вам нужно выбрать набор предметов, суммарная стоимость которых не меньше $$$x$$$, а суммарный вес  — не более $$$\frac{3}{2}W$$$.

Вам необходимо решить задачу для $$$t$$$ наборов входных данных.

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

В первой строке задано количество наборов входных данных. Далее идут сами наборы в следующем формате.

Первая строка описания содержит целые числа $$$n$$$ и $$$W$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le W \le 10^{12}$$$) — количество предметов и заявленная грузоподъёмность рюкзака.

Каждая из следующих $$$n$$$ строк содержит целые числа $$$w_i$$$ и $$$cost_i$$$ ($$$1 \le w_i, cost_i \le 10^6$$$) — вес и стоимость очередного предмета.

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

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

Для каждого набора входных данных выведите, какие предметы нужно взять при ограничении веса $$$\frac{3}{2}W$$$, в следующем формате.

На первой строке выведите количество выбранных предметов $$$k$$$.

На второй строке перечислите номера выбранных предметов $$$i_1, i_2, \ldots, i_k$$$ ($$$1 \le i_j \le n$$$). Выведенные вами номера $$$i_j$$$ должны быть различны. Предметы нумеруются от $$$1$$$ до $$$n$$$ в том порядке, в котором они приведены в тесте.

Если решений несколько, выведите любое из них.

Пример
Входные данные
3
3 10
5 100
5 100
4 99
3 100
97 100
98 101
99 90
3 100
55 100
99 150
200 200
Выходные данные
3
3 1 2 
1
2
1
2