-- knapsack
import Control.Monad
import Data.List

main = do
    [n,capacity] <- map read.words <$> getLine
    goods <- replicateM n (format.map (read).words <$> getLine) :: IO [(Int,Int)]
    print $ answer capacity goods

type Weight = Int
type Value = Int

weight = fst
value = snd

format :: [Int] -> (Weight, Value)
format (a:b:_) = (a,b)

better :: (Weight, Value) -> (Weight, Value) -> (Weight, Value)
better x y = if value x >= value y then x else y

add :: (Weight, Value) -> (Weight, Value) -> (Weight, Value)
add (xw,xv) (yw,yv) = (xw+yw, xv+yv)

answer :: Weight -> [(Weight,Value)] -> Int
answer capacity = snd.head.foldr swag start where
    start = replicate (capacity+1) (0,0)
    swag i ls = zipWith better ls (map (add i) $ drop (weight i) ls)
                    ++ drop (capacity+1-weight i) ls