import Control.Monad

solve n goods w = last $ foldl f initial goods where
  f acc (w, v) = zipWith max acc pick where
    pick = map (v+) $ replicate w (-v) ++ acc
  initial = replicate (w+1) 0

main = do
  [n,w] <- map read.words <$> getLine
  goods <- replicateM n $ (\[a,b]->(a,b)).map read.words <$> getLine
  print $ solve n goods w