{-# LANGUAGE FlexibleContexts #-}

import Control.Applicative
import Data.Array

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  print $ (resolve capa (listArray (0,capa) [0,0..]) goods) ! capa

resolve :: Int -> Array Int Int -> [[Int]] -> Array Int Int
resolve capa capaArr ([v,w]:xs)
  | xs == [] = koushin capaArr [v,w] 0
  | otherwise = resolve capa (koushin capaArr [v,w] 0) xs
  where
    koushin :: Array Int Int -> [Int] -> Int -> Array Int Int
    koushin capaArr [v,w] n
      | n == 0 && capaArr ! w <= v = koushin (capaArr // [( w , v)]) [v,w] (n+1)
      | n + w > snd (bounds capaArr) = capaArr
      | capaArr ! n == 0       = koushin capaArr [v,w] (n+1)
      | capaArr ! (n+w) >= v + (capaArr ! n)  = koushin capaArr [v,w] (n+1)
      | otherwise = koushin (capaArr // [( n + w , v + (capaArr ! n))]) [v,w] (n+1)