시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 243 51 37 21.023%

문제

어느 나라에는, 여러 큐브와 연결된 스위치를 적절한 횟수만큼 눌러 모든 큐브 위에 적힌 숫자를 동일하게 만드는 게임이 있다.

그중 스트레이트 스위치라는 게임이 있다.

스트레이트 스위치 게임은 다음의 규칙을 따른다.

  • 선분 위에 여러 개의 큐브가 일렬로 놓여 있고, 이 큐브 중 특정 큐브들과 연결된 스위치들이 여러 개 존재한다.
  • i 번 스위치를 한 번 누르면 해당 스위치와 연결된 모든 큐브 위의 숫자가 1씩 빠르게 i 번 증가해, 총  i 만큼 증가한다.
  • 큐브 위의 숫자는 0, 1, 2, 3, 4만 존재할 수 있으며 스위치를 눌러 큐브 위의 숫자가 증가하다 4를 초과하면 0으로 즉시 초기화된다.
  • 스위치를 한 번 누를 때, 반드시 단 한 개의 스위치만 누를 수 있다.
  • 같은 번호의 큐브가 한 스위치에 여러 번 연결되어있는 경우는 없다.
  • 각 스위치를 누를 수 있는 횟수의 제한은 없다.
  • 큐브 위에 쓰여 있는 모든 숫자가 동일해지는 순간, 게임은 종료된다.

이 스트레이트 스위치 게임의 국가 대표 선수인 당신은 세계 대회에서 우수한 성적을 거두기 위해 전략을 세워야 한다.

큐브의 개수와 현재 큐브 위에 쓰여 있는 숫자들, 그리고 스위치-큐브 간의 연결 정보가 주어질 때

이 큐브들 위에 쓰여 있는 숫자를 모두 동일하게 만들기 위해 눌러야 하는 스위치의 최소 횟수를 구해보자.

입력

첫 번째 줄에는 큐브의 개수 N과 스위치의 개수 K가 주어진다. (1 ≤ N, K ≤ 8)

두 번째 줄에는 현재 N개의 큐브 위에 쓰여 있는 숫자 aaa3 ... aN 가 한 줄에 주어진다. (0 ≤ ai ≤ 4)

세 번째 줄 부터 K+3번째 줄에는, 1번 스위치부터 K번 스위치까지 각 스위치에 연결된 큐브의 개수(Bm)와, 연결된 큐브의 번호들(bj)이 각 줄 마다 주어진다. (1 ≤ j, B ≤ N, 1 ≤ m, bj ≤ K)

출력

첫 번째 줄에 큐브들 위에 쓰여 있는 숫자를 모두 동일하게 만들기 위해 눌러야 하는 스위치의 최소 횟수를 출력한다.

(단, 주어진 스위치들을 아무리 누르더라도 모든 큐브의 숫자를 동일하게 만들 수 없는 경우에는 -1을 출력한다.)

예제 입력 1

4 2
0 1 0 1
2 1 3
3 1 2 3

예제 출력 1

1

1번 버튼을 누르면 1, 3번째 큐브의 숫자가 1 증가한다. 따라서 모든 큐브의 숫자가 1로 같게 된다.

한 번 미만으로 버튼을 눌러 모든 숫자를 같게 만들 수는 없다. 따라서 정답은 1이다.

예제 입력 2

2 2
1 2
2 1 2
2 1 2

예제 출력 2

-1

모든 스위치를, 몇 번을 누르더라도 큐브 위의 숫자를 모두 같게 할 수 없다. 따라서 -1을 출력해야한다.