Polycarp 玩电脑游戏。在这款游戏中,玩家召唤魔法小兵大军,然后互相战斗。
Polycarp 可以召唤 $$$n$$$ 不同的小兵。第$$$i$$$小兵的初始力量等级为$$$a_i$$$,当它被召唤时,所有先前召唤的小兵的力量等级都会增加$$$b_i$$$。可以按任何顺序召唤仆从。
不幸的是,Polycarp 无法控制超过 $$$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$$$ — Polycarp 必须执行的动作数量 ($$$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$$$。
如果有多个最佳序列,则打印其中任何一个。
示例
输入 #1
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
输出 #1
4 2 1 -1 5 1 2 5 5 4 3 2 1
注意
考虑示例测试。
在第一个测试用例中,波利卡普可以召唤力量等级为$$$7$$$的随从$$$2$$$,然后召唤随从$$$1$$$,这将使前一个随从的力量等级增加$$$3$$$,然后摧毁随从$$$1$$$,最后召唤随从$$$5$$$。此后,波利卡普将拥有两个力量等级为 $$$10$$$ 的随从。
在第二个测试用例中,波利卡普只能控制一个随从,因此他应该选择其中最强的一个并召唤它。
在第三个测试用例中,Polycarp 能够召唤并控制所有五个小兵。