import           Control.Monad
import qualified Data.IntMap   as M

readInts :: IO [Int]
readInts = map read . words <$> getLine

main :: IO ()
main = do
    [n, k] <- readInts
    abs <- replicateM n readInts
    print $ solve k abs

solve :: Int -> [[Int]] -> Int
solve n = go n . M.fromListWith (+) . map (\[x, y] -> (x, y))
  where
    go n mp    
      | v <  n = go (n - v) mp1
      | v >= n = k
      where ((k, v), mp1) = M.deleteFindMin mp
