[17471]게리멘더링

import java.util.*;
import java.io.*;
/*
 * 입력 
 * 구역개수, 구역별 사람수, 인접한 구역 수와 연결된 구역의 번호
 * 
 * 출력
 * 두 선거구의 차이 최솟값, 두 선거구로 나눌 수 없다면 -1
 * 
 * 설계 
 * 선거구를 2개로 나눌 수 있는지 확인 
 * 된다면 차이 계산
 * 
 * 
 * 방문한 곳과 안한 곳으로 나눔 -> 조합?
 * 두개의 영역 각각 이어지는지 확인 -> bfs?
 * 이어지면 차이 계산 -> 방문했으면 + 아니면 - 마지막에 절댓값
 * 
 */
public class Main {
	static int N, answer, arr[][], pCnt[];
	static boolean visit[];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		answer = Integer.MAX_VALUE;
		N= Integer.parseInt(br.readLine());
		pCnt = new int[N];
		arr = new int[N][];
		visit = new boolean[1<<N];
		visit[0] = true;
		visit[(1<<N)-1]= true;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			pCnt[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int M = Integer.parseInt(st.nextToken());
			arr[i] = new int[M];
			for(int j=0; j<M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken())-1;
			}
		}
		
		com(0,0);
		if(answer== Integer.MAX_VALUE) answer =-1;
		System.out.println(answer);
		
		
	}

	
	
	
	
	//전체 방문 제외한 모든 조합
	public static void com(int start, int bVisit) {
		if(!visit[bVisit]) {
			areaCheck(bVisit);
			visit[bVisit] = true;
		}
		for(int i=start; i<N; i++) {
			com(start+1, bVisit | 1<<i);
		}
	}
	
	public static void areaCheck(int bitVisit) {
		Queue<Position> q = new LinkedList<>();
		int sum[]= {0,0}, cnt[]= {-1,-1};
		
		boolean visit[][] = new boolean[2][N];
		
		for(int i=0; i<N; i++) {
			if((bitVisit & 1<<i) == 0) {
				cnt[1]++;
				visit[0][i] = true;
				if(sum[1] == 0) {
					sum[1] = pCnt[i];
					q.add(new Position(i,1));
					visit[1][i] =true;
				}
			}else {
				cnt[0]++;
				visit[1][i] = true;
				if(sum[0] == 0) {
					q.add(new Position(i,0));
					sum[0] = pCnt[i];
					visit[0][i] =true;
				}
			}
		}
		
		while(!q.isEmpty()) {
			Position p = q.poll();
			int area = p.area;
			int num = p.num;
			
			for(int i : arr[num]) {
				if(!visit[area][i]) {
					q.offer(new Position(i,area));
					visit[area][i] =true;
					sum[area]+=pCnt[i];
					cnt[area]--;
				}
				
			}
			
		}
		
		if(cnt[0] ==0 && cnt[1]==0) {
			answer = Math.min(answer, Math.abs(sum[0]-sum[1]));
		}
		
		
	}
	
	static class Position{
		int num;
		int area;
		
		public Position(int num, int area) {
			super();
			this.num = num;
			this.area = area;
		}
		
	}
}