{-# 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 $ toAns $ solve2 [initState] mvs mvs
      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(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))

move2::GameState->Move->GameState
move2 (GameState (Tray ta tb tc) hi) mv=
  case mv of
    AB->(GameState (Tray (tail ta) (head ta:tb) tc) (Just AB))
    BA->(GameState (Tray  (head tb:ta) (tail tb) tc) (Just BA))
    BC->(GameState (Tray  ta (tail tb) (head tb:tc)) (Just BC))
    CB->(GameState (Tray  ta (head tc:tb) (tail tc)) (Just CB))

toAns::Maybe Int ->Int
toAns x=fromMaybe (-1) x

solve2::[GameState]->Int->Int->Maybe Int
solve2 _ _ (-1) =Nothing
solve2 states lim !n=
  case () of
    _ |any isClear states->Just (lim-n)
      |otherwise-> solve2 (concatMap (\s->map (move2 s) (canMove s)) states) lim (n-1)

canMove::GameState->[Move]
canMove (GameState tr Nothing)=canMove' tr
canMove (GameState tr (Just mv))=delete (rev mv) (canMove' tr)

rev::Move->Move
rev AB=BA
rev BA=AB
rev BC=CB
rev CB=BC

canMove'::Tray->[Move]
canMove' (Tray ta tb tc)=
      case (ta,tb,tc) of
        ([],[],_)->[CB]
        (_,[],[])->[AB]
        ([],_,[])->[BA,BC]
        ((a:as),(b:bs),[])->(if a>b then AB else BA):BC:[]
        (_,[],_)->[AB,CB]
        ([],(b:bs),(c:cs))->(if b>c then BC else CB):BA:[]
        ((a:as),(b:bs),(c:cs))->(if a>b then AB else BA):(if b>c then BC else CB):[]

{-
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 =let !q=unsafePerformIO $ print (record,n,(length states))in
      case () of
        _ |null states -> Just record
          |record <= m-n ->Just record
          |0>n ->Nothing
          |otherwise ->      let upds=concatMap (\s->moves (noReturn s) s) states
                                 sorted=nub . sortOn lenInclease1 $ upds
                                 std=lenInclease1 $ head sorted
                                 sieved= takeWhile ((==std) . lenInclease1) sorted
                                 (str,noStr)=split (isStraight1 . (`isStraight` l)) sieved
                                 anss=map ((+(m-n+1)) . solveS1 . (`isStraight` l)) str
                             in solve' (minimum (record:anss)) m sieved (n-1) l

-}
canClear::GameState->Int->Int->Bool
canClear (GameState (Tray ta tb tc) _) n lim=(lim+1)*3 >= (solveS $ n - (max (lenInclease ta) (lenInclease tc)))

lenInclease1::GameState->Int
lenInclease1 (GameState (Tray ta _ tc) _)=max (lenInclease ta) (lenInclease tc)

lenInclease::[Int]->Int
lenInclease list=length . takeWhile id $ zipWith ($) (map (==) [1..]) (reverse list)

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

Measured memory_bytes: 4172