Team Division

A mock internal security hackathon will be held soon. The N participating employees will be split into an attack team (hacking) and a defense team (security). Every employee's attack power and defense power were quantified from the company's previous internal hacking practice contest and stored in a database. Let the attack power of employee $i$ be $A_i$ and the defense power be $B_i$.

There are $2^N$ ways to split the N employees into the two teams. We want the most suitable split. The fitness score is computed as follows. First, add the sum of attack power of the employees in the attack team and the sum of defense power of the employees in the defense team. Then subtract the penalties described below.

The company currently has M task forces. Each task force contains between 2 and N employees. If two employees in the same task force are assigned to different teams, the fitness score is reduced by that task force's penalty weight. The penalty is applied separately to every pair of employees in the task force.

For example, let N = 3 and the employees have the following attack and defense power.

• Employee 1: attack 10, defense 0
• Employee 2: attack 10, defense 5
• Employee 3: attack 5, defense 5

Suppose there is one task force containing employees 1 and 2, with penalty weight 100. If the attack team is {1, 2} and the defense team is {3}, the attack sum is 20, the defense sum is 5, and the penalty is 0, so the fitness is 25. If the attack team is {1} and the defense team is {2, 3}, the attack sum is 10, the defense sum is 10, and the penalty is 100, so the fitness is -80. If the attack team is {1, 2, 3} and the defense team is empty, the attack sum is 25, the defense sum is 0, and the penalty is 0, so the fitness is 25. The maximum fitness here is 25, and the two splits above achieve it. Assigning all employees to the attack team or all of them to the defense team is also allowed. The security staff are assigned to the teams separately, so they are not part of this calculation.

The first line contains the number of test cases $T$.

The first line of each test case contains $N$ and $M$, separated by a space.

The next $N$ lines each contain the attack power and defense power of one employee, separated by a space.

The next $2M$ lines describe the $M$ task forces, two lines each. The first line of task force $i$ contains $K_i$, the number of employees in the task force, and $S_i$, the penalty weight, separated by a space. The penalty weight $S_i$ is the penalty applied to each pair of employees in task force $i$ who are assigned to different teams. The second line contains the $K_i$ employee numbers in task force $i$, separated by spaces. The employee numbers within one task force are all distinct.

For each test case, print two lines.

On the first line, print the maximum fitness score that can be achieved.

On the second line, print the attack team. The first number is the size of the attack team, followed by the employee numbers in the attack team, separated by spaces.

If several splits achieve the maximum fitness, print any of them. The employee numbers may be printed in any order.

$1 \le T \le 10$

$0 \le A_i, B_i \le 1{,}000{,}000$

$2 \le K_i \le N$

$1 \le S_i \le 1{,}000$

An employee may belong to several task forces.