{-# LANGUAGE BangPatterns #-} import Control.Monad.State import Data.Char import Data.Coerce import Data.IORef import Data.Word import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Unboxed as VU main :: IO () main = do [n, d] <- map (read :: String -> Int) . words <$> getLine [t1, k1] <- map (read :: String -> Int) . words <$> getLine t <- newIORef t1 k <- newIORef (k1 - d) rep (n - 1) $ \_ -> do qs <- seqInput 2 itemt <- readIORef t itemk <- readIORef k writeIORef t (max (itemt + qs VU.! 0) (itemk + qs VU.! 0 - d)) writeIORef k (max (itemk + qs VU.! 1) (itemt + qs VU.! 1 - d)) print =<< max <$> readIORef t <*> readIORef k type CParser a = StateT BSC8.ByteString Maybe a runCParser :: CParser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString) runCParser = runStateT {-# INLINE runCParser #-} int :: CParser Int int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace {-# INLINE int #-} seqInput :: Int -> IO (VU.Vector Int) seqInput n = VU.unfoldrN n (runCParser int) <$> BSC8.getLine {-# INLINE seqInput #-} stream :: Monad m => Int -> Int -> VFSM.Stream m Int stream !l !r = VFSM.Stream step l where step x | x < r = return $ VFSM.Yield x (x + 1) | otherwise = return $ VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] stream #-} rep :: Monad m => Int -> (Int -> m ()) -> m () rep n = flip VFSM.mapM_ (stream 0 n) {-# INLINE rep #-}