import Control.Applicative
import Data.Array
import Data.Maybe

main = do
    [n,w] <- map read . words <$> getLine
    vws <- map (map read . words) . lines <$> getContents
    print $ solve w vws

solve :: Int -> [[Int]] -> Int
solve mw vws = maximum . elems $ foldl f initial vws
    where
        initial = listArray (0,mw) $ repeat 0
        f xs [v,w] = array (0,mw) [(i,val) | 
            i <- [0..mw],
            let val = if i < w 
                        then xs ! i
                        else let v1 = xs ! i
                                 v2 = v + xs ! (i-w)
                              in max v1 v2
            ]