TV 스위치

Dave에게는 오래된 텔레비전이 있고, 이 텔레비전의 기계식 스위치 몇 개는 더 이상 예전처럼 동작하지 않는다.

텔레비전이 새것이었을 때는 올라와 있는 스위치 하나를 누르면 그 스위치만 눌린 상태가 되고 나머지 스위치는 모두 올라왔다. 하지만 지금은 올라와 있는 스위치를 눌렀을 때 그 스위치는 눌린 상태가 되지만, 미리 정해진 일부 스위치만 올라오고 다른 스위치의 상태는 그대로 유지된다.

Dave는 각 스위치를 눌렀을 때 어떤 스위치들이 올라오는지 알고 있다. 초기 스위치 상태가 주어졌을 때, 마지막에 3번 스위치만 눌려 있고 나머지 모든 스위치가 올라와 있도록 만드는 가장 짧은 스위치 누름 횟수를 구하라.

첫째 줄에 텔레비전 스위치의 개수 N (3 <= N <= 20)이 주어진다.

둘째 줄에는 공백으로 구분된 이진 숫자 N개가 주어진다. i번째 숫자는 i번 스위치의 초기 상태를 나타내며, 0은 올라와 있는 상태, 1은 눌려 있는 상태를 뜻한다.

다음 N개의 줄은 각 스위치를 눌렀을 때 올라오는 스위치들을 나타낸다. 스위치 M에 해당하는 줄은 정수 K로 시작하고, 이어서 오름차순으로 정렬된 스위치 번호 K개가 주어진다. 이 번호들은 스위치 M을 눌렀을 때 올라오는 스위치들이다. 스위치 번호는 1부터 N까지이다. 어떤 스위치도 자기 자신을 올리지는 않으며, 아무 스위치도 올리지 않을 수 있다.

입력은 항상 해가 존재하도록 주어진다.

3번 스위치만 눌려 있고 나머지 모든 스위치가 올라와 있는 상태를 만들기 위해 필요한 가장 짧은 스위치 누름 횟수를 출력한다.