Yêu cầu

Có \(n\) cốc kích thước khác nhau trên ba khay A, B, C. Trên mỗi khay, cốc nhỏ hơn nằm dưới cốc lớn hơn. Mỗi lần chỉ chuyển cốc trên cùng; không được đặt cốc nhỏ lên cốc lớn; chỉ được chuyển giữa A–B hoặc B–C, không trực tiếp giữa A–C.

Hãy tìm số bước ít nhất để gom tất cả cốc lên A hoặc C. Nếu không thể thực hiện trong nhiều nhất \(m\) bước, in \(-1\).

Dữ liệu vào

Dòng đầu chứa \(n,m\). Ba dòng tiếp theo mô tả A, B, C: số đầu là lượng cốc, sau đó là kích thước các cốc theo thứ tự tăng dần.

Dữ liệu ra

In số bước nhỏ nhất, hoặc -1.

Ràng buộc

• \(1\le n\le15\).
• \(1\le m\le15000000\).
• Các kích thước \(1,2,\ldots,n\) xuất hiện đúng một lần.

Ví dụ

3 10
1 1
1 3
1 2

7