팀 가르기

곧 사내 모의 보안 해커톤 대회가 열린다. 참가하는 $N$명의 임직원은 공격팀(해킹 담당)과 방어팀(보안 담당)으로 나뉜다. 모든 임직원의 공격력과 방어력은 이전 사내 해킹 연습 대회를 통해 수치화되어 데이터베이스에 저장되어 있다. $i$번째 임직원의 공격력을 $A_i$, 방어력을 $B_i$라 하자.

$N$명의 임직원을 공격팀과 방어팀으로 나누는 방법은 $2^N$가지이다. 이 중 가장 적합한 방법으로 팀을 나누려고 한다. 적합도는 다음과 같이 계산한다. 먼저 공격팀에 배정된 임직원들의 공격력 합과 방어팀에 배정된 임직원들의 방어력 합을 더한다. 그다음 아래에서 설명하는 감점을 뺀다.

현재 사내에는 $M$개의 태스크 포스가 있으며, 각 태스크 포스에는 2명 이상 $N$명 이하의 임직원이 속해 있다. 같은 태스크 포스에 속한 두 임직원이 서로 다른 팀에 배정되면, 그 태스크 포스의 감점도만큼 적합도가 줄어든다. 감점은 태스크 포스에 속한 모든 임직원 쌍에 대해 각각 적용한다.

예를 들어 $N = 3$이고 임직원의 공격력과 방어력이 다음과 같다고 하자.

• 임직원 1: 공격력 10, 방어력 0
• 임직원 2: 공격력 10, 방어력 5
• 임직원 3: 공격력 5, 방어력 5

태스크 포스가 하나 있고 임직원 1과 2가 속해 있으며, 감점도는 100이라 하자. 공격팀을 {1, 2}, 방어팀을 {3}으로 배정하면 공격력 합은 20, 방어력 합은 5, 감점은 0이므로 적합도는 25이다. 공격팀을 {1}, 방어팀을 {2, 3}으로 배정하면 공격력 합은 10, 방어력 합은 10, 감점은 100이므로 적합도는 -80이다. 공격팀을 {1, 2, 3}, 방어팀을 비워 두면 공격력 합은 25, 방어력 합은 0, 감점은 0이므로 적합도는 25이다. 이 경우 최대 적합도는 25이며, 위의 두 방법으로 달성할 수 있다. 모든 임직원을 공격팀에 배정하거나 모든 임직원을 방어팀에 배정하는 것도 가능하다. 사내 보안팀은 별도로 적절히 나뉘어 배정될 예정이므로 계산에 포함하지 않는다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$과 $M$이 공백으로 구분되어 주어진다.

다음 $N$줄에는 각 임직원의 공격력과 방어력이 공백으로 구분되어 주어진다.

다음 $2M$줄에는 $M$개의 태스크 포스 정보가 두 줄씩 주어진다. 태스크 포스 $i$의 첫 줄에는 소속 임직원 수 $K_i$와 감점도 $S_i$가 공백으로 구분되어 주어진다. 감점도 $S_i$는 태스크 포스 $i$에 속한 임직원 한 쌍이 서로 다른 팀에 배정되었을 때 적용되는 감점의 크기이다. 두 번째 줄에는 태스크 포스 $i$에 속한 임직원 번호 $K_i$개가 공백으로 구분되어 주어진다. 같은 태스크 포스 안의 임직원 번호는 모두 다르다.

각 테스트 케이스에 대해 두 줄을 출력한다.

첫 줄에는 달성할 수 있는 최대 적합도를 출력한다.

둘째 줄에는 공격팀을 출력한다. 첫 수는 공격팀에 속한 임직원 수이고, 그 뒤에 공백으로 구분하여 임직원 번호를 이어서 출력한다.

최대 적합도를 달성하는 방법이 여럿이면 그중 아무 방법이나 출력해도 된다. 임직원 번호는 임의의 순서로 출력해도 된다.

$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$

한 임직원은 여러 태스크 포스에 속할 수 있다.