import Control.Monad
import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)
import Data.List

readIntsLines :: IO [[Int]]
readIntsLines = map (map (fst . fromJust . BC.readInt) . BC.words) . BC.lines <$> BC.getContents

solve :: Int -> [[(Bool, Int, Int, Int)]] -> [Int]
solve _ [] = []
solve g (pt:pts) = count g pt:solve g pts

count :: Int -> [(Bool, Int, Int, Int)] -> Int
count g pt = if g <= result
             then num
             else if result2 /= 0 then result2 else 10 ^ 7
  where result = sum $ map calc pt
        result2 = num + rest (g - result) pt
        num = sum $ map countNum pt
        calc (enable, point, count, bonus) = if enable then point * count + bonus else 0
        countNum (enable, _, count, _) = if enable then count else 0
        

rest :: Int ->  [(Bool, Int, Int, Int)] -> Int
rest g pt = target
  where enable (b, _, _, _) = not b
        compPoint (_, p1, _, _) (_, p2, _, _) = compare p1 p2
        filtered = sortBy compPoint $ filter enable pt
        target = if null filtered
                 then 0
                 else let (_, point, count, _) = last filtered in
                      if g `div` point >= count
                      then 10 ^ 7
                      else g `div` point

to2ple [x, y] = (x, y)
to4ple ((a, b), (c, d)) = (d, c, a, b)

main :: IO ()
main = do
  [d, g] <- map read . words <$> getLine
  pcs <- map to2ple <$> readIntsLines
  let ds = zip [100,200..] <$> replicateM d [True, False]
  print . minimum . solve g $ map (map to4ple) $ zip pcs <$> ds
