module Main where

import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as B
import Control.Monad
    
solve :: Int    -- Max Weight
     -> [[Int]] -- [[value, weight]]
     -> Int     -- Max Value
solve w = iter $ take (w+1) $ repeat 0 where
    iter (m:ms) [] = m
    iter mem ([value, weight]:xs) = iter mem' xs where
        iter2 [] _ = []
        iter2 ml@(m:ms) w
            | w >= weight = max (ml !! (length ms - w + weight) + value) m : iter2 ms (w-1)
            | otherwise  = m : iter2 ms (w-1)
        mem' = iter2 mem w
    
readLine:: B.ByteString -> [Int]
readLine s = map (fst . fromJust . B.readInt) (B.words s)

readLines :: [B.ByteString] -> [[Int]]
readLines [] = []
readLines (s:ss) = readLine s : readLines ss

main :: IO() 
main = do
    contents <- B.getContents
    let lines = B.lines contents
        [n,w] = readLine (head lines)
        l   = readLines (tail lines)
        ans = solve w l
    print ans

