import Data.Maybe import Data.List import Data.Function import Control.Applicative import Debug.Trace main :: IO () main = do n <- read <$> getLine c <- read <$> getLine v <- read <$> getLine s <- map read . words <$> getLine t <- map read . words <$> getLine y <- map read . words <$> getLine m <- map read . words <$> getLine print $ no1 n c v s t y m no1 :: Int -> Int -> Int -> [Int] -> [Int] -> [Int] -> [Int] -> Int no1 n c v s t y m = fromMaybe (-1) $ no1' n c v s t y m no1' :: Int -> Int -> Int -> [Int] -> [Int] -> [Int] -> [Int] -> Maybe Int no1' n c _ s t y m = maybeMinimum $ map time $ filter (\a -> place a == n) $ foldl (\a b -> b a) [PlaceCost { place = 1, coin = c, time = 0 }] $ map applyRoute $ sortBy (compare `on` from) $ createRouteList s t y m data PlaceCost = PlaceCost { place :: !Int , coin :: !Int , time :: !Int } deriving (Show) data Route = Route { from :: !Int , to :: !Int , cost :: !Int , rtime :: !Int } deriving (Show) createRouteList :: [Int] -> [Int] -> [Int] -> [Int] -> [Route] createRouteList = zipWith4 Route maybeMinimum :: (Ord a) => [a] -> Maybe a maybeMinimum [] = Nothing maybeMinimum x = Just $ minimum x applyRoute :: Route -> [PlaceCost] -> [PlaceCost] applyRoute _ [] = [] applyRoute r (x:xs) | placeComp == GT = applyRoute r xs | placeComp == LT = x : applyRoute r xs | remainCoin < 0 = x : applyRoute r xs | otherwise = minTimeAdd PlaceCost { place = to r, coin = remainCoin , time = tookTime } $ x : applyRoute r xs where remainCoin = coin x - cost r tookTime = time x + rtime r placeComp = from r `compare` place x minTimeAdd :: PlaceCost -> [PlaceCost] -> [PlaceCost] minTimeAdd pc pcs | null filterPcs = pc : pcs | time pc > time (head filterPcs) = pcs | otherwise = pc : dropWhile samePlaceCoin pcs where filterPcs = filter samePlaceCoin pcs samePlaceCoin a = place pc == place a && coin pc == coin a