Задача №114865. Задача о прочном рюкзаке
Задача о рюкзаке — классическая задача информатики.
Её формулировка такова: есть \(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
2 1 2 1 2 1 2