import qualified Control.Monad as M
import qualified Data.List as L
import Data.Maybe (fromJust)
data Turn = Sunuke | Sumeke deriving (Show, Eq)
type Point = Int
type Stack = ([Int], [Int])
type Game = State (Turn, Stack, Point) Point
main = do
_ <- getLine
as <- map read . words <$> getLine
bs <- map read . words <$> getLine
print $ evalState run (Sunuke, (rSort as, rSort bs), 0)
rSort = L.sortBy (flip compare)
run :: Game
run = do
(trn, stc, p) <- get
let (stc', p') = pop stc
if p' == Nothing
then return $ p
else if trn == Sunuke
then return $ evalState run (Sumeke, stc', p + fromJust p')
else return $ evalState run (Sunuke, stc', p)
pop :: Stack -> (Stack, Maybe Point)
pop ([] , [] ) = (([], []), Nothing)
pop (a:as, [] ) = (([], []), Just a)
pop ([] , b:bs) = (([], []), Just b)
pop (a:as, b:bs) = if a > b
then ((as, b:bs), Just a)
else ((a:as, bs), Just b)
-- State.hs
newtype State s x = State { runState :: s -> (x, s) }
instance Functor (State s) where
fmap = M.liftM
instance Applicative (State s) where
pure x = State $ \s -> (x, s)
(<*>) = M.ap
instance Monad (State s) where
m >>= k = State $ \s ->
let (x, s0) = runState m s
in runState (k x) s0
get :: (State s) s
get = State $ \s -> (s, s)
put :: s -> (State s) ()
put s = State $ \_ -> ((), s)
state :: (s -> (a, s)) -> (State s) a
state f = do
s <- get
let (a, s') = f s
put s'
return a
modify :: (s -> s) -> (State s) ()
modify f = get >>= put . f
gets :: (s -> a) -> (State s) a
gets f = get >>= return . f
evalState :: State s x -> s -> x
evalState = (fst .) . runState
execState :: State s x -> s -> s
execState = (snd .) . runState