CF1354F Summoning Minions

Polycarp 正在玩一款电脑游戏。在这款游戏中，玩家可以召唤魔法随从军队，随后这些随从会互相战斗。 Polycarp 可以召唤 $n$ 个不同的随从。第 $i$ 个随从的初始战斗力为 $a_i$，当它被召唤时，所有之前已被召唤的随从的战斗力都会增加 $b_i$。随从的召唤顺序可以任意选择。 然而，Polycarp 同时最多只能控制 $k$ 个随从。为了摆脱不需要的随从，他可以在召唤后将其销毁。每个随从只能被召唤（和销毁）一次。 Polycarp 的目标是召唤出最强大的军队。具体来说，他希望最大化自己控制的所有随从（即已召唤且未被销毁的随从）的战斗力之和。 请帮助 Polycarp 制定一个行动计划，召唤出最强大的军队！

第一行包含一个整数 $T$（$1 \le T \le 75$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 75$），分别表示可召唤的随从数量和 Polycarp 最多能控制的随从数量。 接下来的 $n$ 行，每行包含两个整数 $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, \ldots, o_m$，其中 $o_i$ 表示第 $i$ 个操作： - 如果第 $i$ 个操作是召唤第 $x$ 个随从，则 $o_i = x$； - 如果第 $i$ 个操作是销毁第 $x$ 个随从，则 $o_i = -x$。 每个随从最多只能被召唤一次，且不能在被召唤前销毁（显然也不能被销毁多次）。在每次操作后，Polycarp 控制的随从数量都不能超过 $k$。 如果存在多组最优方案，输出任意一组即可。

请参考样例测试。 在第一个测试用例中，Polycarp 可以先召唤编号为 $2$ 的随从，其战斗力为 $7$，然后召唤编号为 $1$ 的随从，这会使之前的随从战斗力增加 $3$，接着销毁编号为 $1$ 的随从，最后召唤编号为 $5$ 的随从。此时，Polycarp 将拥有两个战斗力为 $10$ 的随从。 在第二个测试用例中，Polycarp 只能控制一个随从，因此他应选择最强的一个进行召唤。 在第三个测试用例中，Polycarp 可以召唤并控制全部五个随从。 由 ChatGPT 4.1 翻译