Поликарп играет в компьютерную игру. В этой игре игроки призывают армии магических существ и сражаются с армиями существ других игроков.
Поликарп может призвать $$$n$$$ разных существ, $$$i$$$-е существо изначально имеет силу $$$a_i$$$; кроме того, когда Поликарп призывает его, оно увеличивает на $$$b_i$$$ силу всех ранее призванных существ (исключая себя). Поликарп может призывать существ в любом порядке.
Однако под контролем Поликарпа может находиться не более $$$k$$$ существ одновременно. Поэтому, помимо призыва существ, он может уничтожать ранее призванных существ. Каждое существо может быть призвано (а, значит, и уничтожено) не более одного раза.
Цель Поликарпа — собрать максимально сильную армию существ. Он хочет, чтобы после всех его действий суммарная сила всех призванных (но не уничтоженных) им существ была максимально возможной.
Помогите Поликарпу составить оптимальную последовательность действий, чтобы собрать максимально сильную армию!
В первой строке задано одно целое число $$$T$$$ ($$$1 \le T \le 75$$$) — количество наборов тестовых данных.
Каждый набор тестовых данных начинается строкой, содержащей два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 75$$$) — количество существ, доступных для призыва, и максимальное количество существ, которые могут одновременно быть под контролем Поликарпа, соответственно.
Затем следуют $$$n$$$ строк, $$$i$$$-я из которых содержит $$$2$$$ целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i \le 10^5$$$, $$$0 \le b_i \le 10^5$$$) — параметры $$$i$$$-го существа.
Для каждого набора тестовых данных выведите оптимальную последовательность действий в следующем формате:
Сначала выведите $$$m$$$ — количество действий, которые должен совершить Поликарп ($$$0 \le m \le 2n$$$). После этого выведите $$$m$$$ целых чисел $$$o_1$$$, $$$o_2$$$, ..., $$$o_m$$$, где $$$o_i$$$ описывает $$$i$$$-е действие следующим образом: если $$$i$$$-е действие — это «призвать существо $$$x$$$», то $$$o_i = x$$$, а если $$$i$$$-е действие — это «уничтожить существо $$$x$$$», то $$$o_i = -x$$$. Каждое существо может быть призвано не более одного раза и не может быть уничтожено, если оно еще не призвано (или уже уничтожено). После каждого действия под контролем Поликарпа должно быть не более $$$k$$$ существ.
Если оптимальных последовательностей действий несколько, выведите любую из них.
3 5 2 5 3 7 0 5 0 4 0 10 0 2 1 10 100 50 10 5 5 1 5 2 4 3 3 4 2 5 1
4 2 1 -1 5 1 2 5 5 4 3 2 1
Рассмотрим пример из условия.
В первом наборе тестовых данных можно сначала вызвать существо $$$2$$$ с силой $$$7$$$, затем призвать существо $$$1$$$, которое увеличит силу предыдущего существа на $$$3$$$, после этого уничтожить существо $$$1$$$ и поставить существо $$$5$$$. В итоге у Поликарпа будут два существа с силой $$$10$$$.
Во втором наборе тестовых данных у Поликарпа не может быть более одного существа под контролем, поэтому достаточно выбрать самое сильное существо и призвать его.
В третьем наборе тестовых данных Поликарп может призвать всех существ, никого не уничтожая.
