세 트레이 위의 컵 옮기기

크기가 모두 다른 $n$개의 컵과 3개의 트레이 A, B, C가 있습니다. 각 컵은 세 트레이 중 한 곳에 몇 개씩 한 줄로 쌓여 있습니다. 어느 트레이에서든 가장 작은 컵이 맨 아래에 놓이고, 그 위에 두 번째로 작은 컵, 그 위에 세 번째로 작은 컵... 이렇게 작은 것부터 큰 것 순서로 엎어서 겹쳐 쌓여 있습니다. 따라서 한 트레이에서 맨 위에 있는 컵은 그 트레이에서 가장 큰 컵입니다.

아래 그림의 오른쪽은 $n = 5$개의 컵이 트레이 A, B, C에 각각 2개, 0개, 3개 쌓여 있는 상태를 나타냅니다.

컵의 초기 상태가 주어졌을 때, 다음 규칙 1~3을 지키면서 모든 컵을 트레이 A 또는 C 중 한 곳으로 옮기려면 최소 몇 번 옮겨야 하는지 구하려고 합니다.

• (규칙 1) 한 번에 컵 하나만 옮길 수 있으며, 그것은 해당 트레이에서 맨 위에 있는 컵(즉, 가장 큰 컵)입니다.
• (규칙 2) 큰 컵 위에 작은 컵을 겹쳐 놓을 수 없습니다. 즉, 옮기는 컵은 빈 트레이에 놓거나 자기보다 작은 컵 위에만 놓을 수 있습니다.
• (규칙 3) 컵 하나를 직접 옮기는 것은 A에서 B, B에서 A, B에서 C, C에서 B로만 허용되며, A에서 C로 또는 C에서 A로 직접 옮기는 것은 허용되지 않습니다.

$n$개의 컵의 초기 상태와 정수 $m$이 주어졌을 때, $m$번 이하의 이동으로 A 또는 C 중 한 트레이에 모든 컵을 모아 쌓을 수 있는지 판정하고, 가능하면 이동 횟수의 최솟값을, 불가능하면 -1을 출력하는 프로그램을 작성하세요.

첫째 줄에 $n$과 $m$이 공백으로 구분되어 주어집니다 ($1 \le n \le 15$, $1 \le m \le 15000000$). 둘째, 셋째, 넷째 줄은 각각 트레이 A, B, C의 상태를 나타냅니다. 각 줄은 먼저 그 트레이에 쌓인 컵의 개수를 나타내는 정수로 시작하고, 이어서 그 컵들의 크기가 작은 순(오름차순)으로 주어집니다. 크기는 $1$부터 $n$까지의 정수를 세 트레이에 나누어 놓은 것으로, 각 크기는 정확히 한 번씩 나타납니다.

모든 컵을 트레이 A 또는 C 중 한 곳에 모으는 데 필요한 이동 횟수의 최솟값을 한 줄에 출력합니다. $m$번 이하로는 불가능하면 -1을 출력합니다.