import qualified Data.ByteString.Char8 as BC
import Data.Maybe
import Data.List
import Data.Function (on)

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

data Item = Item { weight :: Int, value :: Int }
  deriving Show

solve :: Int -> [Item] -> [Item]
solve maxWeight = snd . last . foldl' step initial
  where initial = replicate (maxWeight + 1) empty
        empty = (0, [])
        step previous item = result
          where result = zipWith choose accepted rejected
                accepted = shift ++ map addItem previous
                rejected = previous
                addItem (v, items) = (v + value item, item : items)
                choose a b = maximumBy (compare `on` fst) [a, b]
                shift = replicate (weight item) empty

main :: IO ()
main = do
  [n, weight] <- map read . words <$> getLine
  let toItem [w, v] = Item { weight = w, value = v }
  items <- map toItem <$> readIntsLines
  print . sum . map value $ solve weight items