{-# LANGUAGE BangPatterns#-}
module Main where

import System.IO.Unsafe
import Data.List
import Data.Maybe
import Control.Monad
import Data.Functor

main :: IO ()
main = do
  (cups,mvs) <- getNM
  unless (cups==0 && mvs==0) $
    do
      initState <- getState
      print $ solve mvs initState cups
      main
  where
    getNM::IO (Int,Int)
    getNM=do
       (n:m:_)<-map read . words <$> getLine
       return (n,m)
    getTray::IO [Int]
    getTray=do
      (n:try) <- map read . words <$> getLine
      return $ reverse $ take n try
    getState::IO GameState
    getState=do
      [ta,tb,tc] <-replicateM 3 getTray
      return $ GameState (Tray ta tb tc) Nothing

data Move=AB|BA|BC|CB deriving(Eq,Show)

data Tray=Tray {trayA::[Int]
              , trayB::[Int]
              , trayC::[Int]
               }deriving(Eq,Show)

data GameState=GameState {tray::Tray
                        , history::Maybe Move}deriving(Eq,Show)
--instance Eq GameState where
  --(GameState tr1 _)==(GameState tr2 _)=tr1==tr2

solveS1::Straight->Int
solveS1 (ToA x) =solveS x
solveS1 (ToC x)=solveS x
solveS::Int->Int
solveS 0=0
solveS !n=2 + (3 * solveS (n-1))

solve::Int->GameState->Int->Int
solve mvs state len=fromMaybe ( -1) $ solve' maxBound mvs [state] mvs len
  where
    solve'::Int->Int->[GameState]->Int->Int->Maybe Int
    solve' record m states !n l =
      case () of
        _ |null states -> Just record
          |record <= m-n ->Just record
          |0>n ->Nothing
          |otherwise ->      let (str,noStr)=split (isStraight1 . (`isStraight` l)) states
                                 anss=map ((+(m-n)) . solveS1 . (`isStraight` l)) str
                                 upds=concatMap (\s->moves (noReturn s) s) noStr
                             in solve' (minimum (record:anss)) m (del states $ nub upds) (n-1) l



move::Move->GameState->Maybe GameState
move mv (GameState tray hist)=do
  tray' <- move'' mv tray
  return $ GameState tray' (Just mv)
  where
    move''::Move->Tray->Maybe Tray
    move'' AB (Tray ta tb tc)=do
      (ta',tb') <- move' (ta,tb)
      return $ Tray ta' tb' tc
    move'' BA (Tray ta tb tc)=do
      (tb',ta') <- move' (tb,ta)
      return $ Tray ta' tb' tc
    move'' BC (Tray ta tb tc)=do
      (tb',tc') <- move' (tb,tc)
      return $ Tray ta tb' tc'
    move'' CB (Tray ta tb tc)=do
      (tc',tb') <- move' (tc,tb)
      return $ Tray ta tb' tc'
    move'::([Int],[Int])->Maybe([Int],[Int])
    move' ([],_)=Nothing
    move' (x:xs,[])=Just (xs,[x])
    move' (x:xs,tr@(y:ys))
      |x>y =Just (xs,x:tr)
      |otherwise=Nothing

moves::[Move]->GameState->[GameState]
moves mvs state=mapMaybe  (`move` state) mvs

isClear::GameState->Bool
isClear (GameState (Tray _ [] []) _)=True
isClear (GameState (Tray [] [] _) _)=True
isClear _ =False


noReturn::GameState->[Move]
noReturn (GameState _ hi)=noReturn' hi
  where
    noReturn'::Maybe Move->[Move]
    noReturn' (Just x)=filter (/= x) [AB,BA,BC,CB]
    noReturn' Nothing=[AB,BA,BC,CB]

data Straight=No|ToA Int|ToC Int
isStraight::GameState->Int->Straight
isStraight (GameState tr _) x=isStraight' tr x
  where
    isStraight'::Tray->Int->Straight
    isStraight' (Tray [] [] tc) n=ToC 0
    isStraight' (Tray ta [] []) n=ToA 0
    isStraight' (Tray ta [] tc) n=
      let [lenA,lenC]=map length [ta,tc] in
      case () of
        _ |head tc==n && head ta== n-lenC  ->ToA lenC
          |head ta==n && head tc== n-lenA  ->ToC lenA
          |otherwise->No
    isStraight' _ _=No

isStraight1::Straight->Bool
isStraight1 No=False
isStraight1 _=True

split::(a->Bool)->[a]->([a],[a])
split f list=foldr (\x (ts,fs)->if f x then (x:ts,fs) else (ts,x:fs)) ([],[]) list

del::Eq a=>[a]->[a]->[a]
del delList target=delList ++ filter (not . (`elem` delList)) target