← 返回题目列表

Codeforces · 1354/F

F. 召唤小兵

中文机器翻译题面 查看原题

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 能够召唤并控制所有五个小兵。