팀 가르기

곧 사내 모의 보안 해커톤 대회가 열릴 예정이며 참가하는 N명의 임직원들은 공격팀 (해킹 담당)과 방어팀 (보안 담당)으로 나뉘게 된다. 모든 임직원이 이전에 참여했던 사내 해킹 연습 대회를 통해 각 임직원의 공격력과 방어력은 수치화 되어 데이터베이스에 저장되어있다. 편의상 i번째 임직원의 공격력은 A[i] 방어력은 B[i]라 하자.

총 N명의 임직원을 공격팀과 방어팀으로 나누는 방법은 2N 가지 존재하지만, 이 중 가장 "적합한" 방법으로 팀을 나누려고 한다. 적합성은 수치화 될 수 있는데, 우선 공격팀에 배장된 모든 임직원들의 공격력 총합과 방어팀에 배정된 (나머지) 모든 임직원들의 방어력 총합을 더한 후, 후술될 "감점"을 적용하여 적합도를 점수화 한다. 팀 배정의 감점 요인은 다음과 같다.

현재 사내에는 M개의 태스크 포스가 있으며 각 태스트 포스에는 2명 이상 N명 이하의 임직원이 속해있다. 만약 같은 태스크 포스에 속한 두 임직원이 서로 다른 팀에 배정된다면, 해당 태스크 포스의 "감점도"에 따라 팀 배정의 적합도 점수가 감점된다. 이 감점은 태스크 포스에 속한 모든 임직원 쌍에 대해 각각 적용한다 (예제 참고).

예를 들어 N = 3 이고 각 임직원의 공격력 / 방어력이 아래와 같다고 해보자.

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

아울러 태스크 포스가 하나 있고 임직원 1, 임직원 2 두 사람이 속해있으며, 이 태스크 포스의 감점도는 100이라 하자. 만약 공격팀 = {임직원 1, 임직원 2} 그리고 방어팀 = {임직원 3} 으로 배정할 경우, 공격력 총 합은 10+10 = 20, 방어력 총합 = 5, 감점 = 0점이 되어 적합도는 총 25가 된다. 만약 공격팀 = {임직원 1} 그리고 방어팀 = {임직원 2, 임직원 3} 으로 배정할 경우, 공격력 총 합은 10, 방어력 총합 = 5+5 = 10, 감점 = 100점이 되어 적합도는 총 -80이 된다. 만약 공격팀 = {임직원 1, 임직원 2, 임직원 3} 그리고 방어팀 = {} 으로 배정할 경우, 공격력 총 합은 10+10+5 = 25, 방어력 총합 = 0, 감점 = 0점이 되어 적합도는 총 25가 된다. 이 예제의 경우 최대 팀 배정 적합도는 25이며, 상기한 두 가지 방법으로 배정할 수 있다. 예제에서 보여지듯 모든 임직원을 공격팀에 배정하거나 모든 임직원을 방어팀에 배정하는 것도 가능하다. N명의 임직원 이외에도 사내 보안팀이 적절히 공격팀과 방어팀에 나뉘어 배정될 예정이기 때문에 아무 문제 없다.

입력으로 임직원의 수 N, 태스크 포스의 수 M, 각 임직원의 공격력/방어력, 그리고 각 태스크 포스에 속한 임직원의 정보 및 태스크 포스별 감점이 주어졌을 때,  팀 배정 적합도를 최대로 만들 경우의 적합도를 구하고, 그러한 적합도를 가능케하는 공격팀 배정을 출력하는 프로그램을 작성하시오.

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

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

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

다음 2M줄에 걸쳐 M개의 태스크 포스에 대한 정보가 (각각 두 줄에 걸쳐) 주어진다.

i번째 태스크 포스에 대한 입력은 두 줄에 나누어서 주어지며, 첫 줄은 태스크 포스에 속한 임직원의 수 (Ki)와 해당 태스크 포스에 속한 임의의 임직원 한 쌍이 다른 팀에 배정 되었을 경우 감점이 되는 정도가 (Si) 주어진다.

두 번째 줄에 태스크 포스에 속한 임직원 번호가 (즉, Ki 개의 정수) 공백으로 구분되어 주어진다. 이 때 주어지는 Ki 개의 정수는 모두 다르다 (즉 각각의 태스크 포스 i의 입력에 주어지는 임직원 번호가 중복인 경우는 없다).

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

첫 줄에 최대 달성 가능한 팀 배정 적합도를 출력한다.

다음 줄에 공격팀을 출력하는데, 첫 수는 공격팀을 구성하는 임직원의 수이며 같은 줄에 이어서 임직원 번호를 공백으로 구분하여 출력한다.

최대 적합도를 달성한 방법이 여럿인 경우 그 중 아무 방법이라 출력하여도 된다.

임직원 번호는 임의의 순서로 출력해도 무방하다.

• 1 ≤ T ≤ 10
• 0 ≤ A[i], B[i] ≤ 1,000,000
• 2 ≤ Ki ≤ N
• 1 ≤ Si ≤ 1,000
• 한 임직원이 여러 태스크 포스에 속할 수 있다.