F. XCPC Restart
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After competing in XCPC 2077, you realize that you have no hope of going any further.

You lie on your bed, close your eyes, and recall the scenes where you once fought hard in the contest hall.

Tears still come out. You are not willing to accept this; you feel that your team could have done better.

Suddenly, you wake up and find yourself back on the night before the contest.

Everything that happened before feels like a dream, yet it was so vivid.

You realize that this time, your team still has a chance.

You decide that this time, you will leave no regrets.

You are filled with determination.

Each XCPC contest lasts $$$300$$$ minutes.

There are $$$n$$$ problems. Their numeric indices are $$$1,2,\cdots,n$$$, and their letter indices are $$$\texttt{A},\texttt{B},\cdots$$$ in order.

It is known that problem $$$i$$$ takes $$$t_i$$$ minutes (not necessarily consecutive) to solve, and before solving it you will make exactly $$$d_i$$$ wrong submissions on this problem.

If problem $$$i$$$ cannot be solved even if you try your best, then $$$t_i=301$$$.

It is important to note that your team can work on only one problem in the same minute.

In the final standings, teams that solve more problems are ranked higher. Among teams that solve the same number of problems, those with a smaller penalty time are ranked higher.

Suppose a team solves problem $$$p_i$$$ at minute $$$s_i$$$ ($$$i=1,2,\cdots,m$$$), then the penalty time of this team is $$$$$$ \sum\limits_{i=1}^m(s_i+20d_{p_i}). $$$$$$ You need to find an optimal strategy — a strategy that maximizes the number of solved problems and, subject to that, minimizes the penalty time.

Input

The first line contains a single integer $$$T$$$ ($$$1\le T\le15000$$$), denoting the number of test cases.

For each test case:

  • The first line contains a single integer $$$n$$$ ($$$1\le n\le 26$$$).
  • Each of the next $$$n$$$ lines contains two integers $$$t_i,d_i$$$ ($$$1\le t_i\le 301$$$, $$$0\le d_i\le t_i$$$).
It is guaranteed that the sum of $$$n$$$ over all $$$T$$$ test cases does not exceed $$$202500$$$.
Output

For each test case, output $$$2$$$ or $$$11$$$ lines.

The first line contains two integers, the number of solved problems and the penalty time when using an optimal strategy.

The second line contains a string of length $$$300$$$ describing an optimal strategy:

  • The $$$i$$$-th character is the letter index of the problem your team is working on during minute $$$i$$$. In particular, if your team is not working on any problem during minute $$$i$$$, then the $$$i$$$-th character is -.
  • If, for some problem with numeric index $$$j$$$, the $$$t_j$$$-th occurrence (from left to right) of its letter index appears at position $$$x$$$ in this string, then the problem is considered to be solved at minute $$$x$$$.
Since the string is quite long, you may also split it into $$$10$$$ lines, each containing $$$30$$$ characters, for ease of display. If so, the output for this test case consists of $$$11$$$ lines.

If there are multiple optimal strategies, you only need to output any of them.

Example
Input
2
2
9 9
295 0
3
246 3
37 7
169 4
Output
1 189
AAAAAAAAABBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB-------
------------------------------
------------------------------
BB-----B----------------------
------------------------------
------------------------------
------------------------------
-----------B------------------
2 463
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA