Summoning Minions
Contest: Educational Codeforces Round 87 (Rated for Div. 2)
Difficulty rating: 2500
Tags: constructive algorithms, dp, flows, graph matchings, greedy, sortings

Polycarp plays a computer game. In this game, the players summon armies of magical minions, which then fight each other.

Polycarp can summon $$$n$$$ different minions. The initial power level of the $$$i$$$-th minion is $$$a_i$$$, and when it is summoned, all previously summoned minions' power levels are increased by $$$b_i$$$. The minions can be summoned in any order.

Unfortunately, Polycarp cannot have more than $$$k$$$ minions under his control. To get rid of unwanted minions after summoning them, he may destroy them. Each minion can be summoned (and destroyed) only once.

Polycarp's goal is to summon the strongest possible army. Formally, he wants to maximize the sum of power levels of all minions under his control (those which are summoned and not destroyed).

Help Polycarp to make up a plan of actions to summon the strongest possible army!

Input format:
The first line contains one integer $$$T$$$ ($$$1 \le T \le 75$$$) — the number of test cases.

Each test case begins with a line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 75$$$) — the number of minions availible for summoning, and the maximum number of minions that can be controlled by Polycarp, respectively.

Then $$$n$$$ lines follow, the $$$i$$$-th line contains $$$2$$$ integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le 10^5$$$, $$$0 \le b_i \le 10^5$$$) — the parameters of the $$$i$$$-th minion.

Output format:
For each test case print the optimal sequence of actions as follows:

Firstly, print $$$m$$$ — the number of actions which Polycarp has to perform ($$$0 \le m \le 2n$$$). Then print $$$m$$$ integers $$$o_1$$$, $$$o_2$$$, ..., $$$o_m$$$, where $$$o_i$$$ denotes the $$$i$$$-th action as follows: if the $$$i$$$-th action is to summon the minion $$$x$$$, then $$$o_i = x$$$, and if the $$$i$$$-th action is to destroy the minion $$$x$$$, then $$$o_i = -x$$$. Each minion can be summoned at most once and cannot be destroyed before being summoned (and, obviously, cannot be destroyed more than once). The number of minions in Polycarp's army should be not greater than $$$k$$$ after every action.

If there are multiple optimal sequences, print any of them.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
Consider the example test.

In the first test case, Polycarp can summon the minion $$$2$$$ with power level $$$7$$$, then summon the minion $$$1$$$, which will increase the power level of the previous minion by $$$3$$$, then destroy the minion $$$1$$$, and finally, summon the minion $$$5$$$. After this, Polycarp will have two minions with power levels of $$$10$$$.

In the second test case, Polycarp can control only one minion, so he should choose the strongest of them and summon it.

In the third test case, Polycarp is able to summon and control all five minions.

Example input:
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

Example output:
4
2 1 -1 5
1
2
5
5 4 3 2 1

Editorial:
First of all, let's try to find the best strategy to play minions. All minions should be summoned (if someone is not summoned, summoning and deleting it won't make the answer worse), the resulting number of minions should be exactly $$$k$$$ (if it is less, then we didn't need to delete the last deleted minion). Furthermore, if some minion should be deleted, we can delete it just after it is summoned. All these greedy ideas lead to the following structure of the answer:
• we choose $$$k - 1$$$ minions and summon them in some order;
• we choose $$$n - k$$$ minions which will be summoned and instantly deleted;
• we summon the remaining minion.
Let's analyze how these minions affect the answer. The first minion has power $$$a_i$$$ and does not give bonus to anyone, the second one has power $$$a_i$$$ and gives bonus to one minion, and so on — the $$$j$$$-th minion from the first group adds $$$a_i + (j - 1)b_i$$$ to the answer. Minions from the second group buff $$$k - 1$$$ minions each, so they add $$$b_i(k - 1)$$$ to the answer; and the last minion adds $$$a_i + b_i(k - 1)$$$. Let's unite the first group and the last minion; then we will have two groups of minions — those which are destroyed (the second group) and those which are not destroyed (the first group).
From there, we will have two possible ways to finish the solution:
• there are $$$n$$$ minions and $$$n$$$ positions for them, and for each pair (minion, position) we may calculate the value this pair adds to the answer. After that, we should assign each monster a position in such a way that each position is chosen exactly once, and the sum of values is maximized. It can be done with mincost flows or Hungarian algorithm;
• the minions from the first group should be played in non-descending order of their $$$b_i$$$. Let's sort all minions by $$$b_i$$$ and write the following dynamic programming: $$$dp_{x, y}$$$ is the maximum answer if we considered $$$x$$$ first minions, and $$$y$$$ of them were assigned to the first group. Since the minions are sorted by $$$b_i$$$, whenever we add a minion to the first group, it should add exactly $$$a_i + yb_i$$$ to the answer (and increase $$$y$$$ by $$$1$$$); and if a minion is added to the second group, the answer is increased by $$$(k - 1)b_i$$$.