스트레이트 스위치 게임

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

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

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

• 선분 위에 여러 개의 큐브가 일렬로 놓여 있고, 이 큐브 중 특정 큐브와 연결된 스위치가 여러 개 있다.
• i번 스위치를 한 번 누르면 그 스위치와 연결된 모든 큐브의 숫자가 각각 i만큼 증가한다.
• 큐브의 숫자는 0, 1, 2, 3, 4만 될 수 있으며, 스위치를 눌러 큐브의 숫자 K가 4를 넘으면 K를 5로 나눈 나머지로 즉시 초기화한다.
• 스위치를 한 번 누를 때 반드시 한 개의 스위치만 누를 수 있다.
• 같은 번호의 큐브가 한 스위치에 여러 번 연결되어 있는 경우는 없다.
• 각 스위치를 누를 수 있는 횟수에는 제한이 없다.
• 큐브에 적힌 모든 숫자가 같아지는 순간 게임이 끝난다.

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

큐브의 개수와 현재 큐브에 적힌 숫자, 스위치와 큐브의 연결 정보가 주어질 때, 큐브에 적힌 숫자를 모두 같게 만들기 위해 눌러야 하는 스위치의 최소 횟수를 구해보자.

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

두 번째 줄에는 현재 N개의 큐브에 적힌 숫자 a1 a2 a3 ... aN이 한 줄에 주어진다. (0 ≤ ai ≤ 4)

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

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

(단, 주어진 스위치를 아무리 눌러도 모든 큐브의 숫자를 같게 만들 수 없는 경우에는 -1을 출력한다.)