406007: GYM102215 M Shlakoblock is live!

User Shlakoblock has made a poll for the viewers of his channel, which game he should play on the next stream. $$$n$$$ games are presented in the poll. Every viewer can vote for any subset of these games, but it is not possible to vote for the same game more than once. In the end Shlakoblock will choose a random vote and will stream the game this vote was given for.

Everyone except you has already voted. Now the $$$i$$$-th game has $$$v_i$$$ votes. You estimate the pleasure of viewing the stream of the $$$i$$$-th game as $$$p_i$$$. Which games should you vote for to maximize the expected pleasure of the stream?

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. Descriptions of the test cases follow.

In the first line of each test case there is a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of games.

Each of the next $$$n$$$ lines of this test case contains two integers $$$p_i$$$ and $$$v_i$$$ ($$$0 \le p_i, v_i \le 1000$$$) — the pleasure of the stream of the $$$i$$$-th game and the number of votes it has now.

It is guaranteed that in every test at least one $$$v_i$$$ is positive.

Output $$$3t$$$ lines. The answer for each test should consist of three lines.

In the first line output an irreducible fraction — the maximal possible expected pleasure of the stream.

In the second line output an integer $$$k$$$ ($$$0 \le k \le n$$$) — the number of games to vote for.

In the third line output $$$k$$$ distinct integers from $$$1$$$ to $$$n$$$ — the numbers of games to vote for.

If there are several possible answers, output any of them.

2
5
10 5
4 7
6 3
8 2
2 4
4
1 1000
10 100
100 10
1000 1

6/1
2
1 4 
2555/557
3
2 3 4