Moving Cups Across Three Trays

There are $n$ cups, all of different sizes, and three trays A, B, and C. The cups are stacked in piles on the trays. On every tray the smallest cup is at the bottom, the second-smallest sits on top of it, the third-smallest on top of that, and so on — the cups are stacked upside down from smallest to largest. Hence the topmost cup on a tray is the largest cup on that tray.

The right side of the figure below shows a state with $n = 5$ cups stacked 2, 0, and 3 on trays A, B, and C respectively.

Given the initial arrangement of the cups, we want to find the minimum number of moves needed to gather all cups onto either tray A or tray C while obeying the following rules 1–3.

• (Rule 1) Each move relocates exactly one cup: the topmost cup of a tray (that is, its largest cup).
• (Rule 2) You may not place a smaller cup on top of a larger one. In other words, a moved cup may be placed only on an empty tray or on top of a cup smaller than itself.
• (Rule 3) A single cup may be moved directly only from A to B, B to A, B to C, or C to B. Moving a cup directly from A to C, or from C to A, is not allowed.

Given the initial arrangement of the $n$ cups and an integer $m$, write a program that decides whether all cups can be gathered onto a single tray (A or C) in at most $m$ moves. If it is possible, output the minimum number of moves; otherwise output -1.

The first line contains $n$ and $m$ separated by a space ($1 \le n \le 15$, $1 \le m \le 15000000$). The second, third, and fourth lines describe trays A, B, and C respectively. Each line begins with an integer giving the number of cups on that tray, followed by the sizes of those cups in ascending order. The sizes are the integers from $1$ to $n$ partitioned among the three trays, each size appearing exactly once.

Print, on a single line, the minimum number of moves needed to gather all cups onto tray A or tray C. If this cannot be done in at most $m$ moves, print -1.