import Control.Applicative
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 . map snd $ foldl f [] vws
    where
        f :: [(Int,Int)] -> [Int] -> [(Int,Int)]
        f xs [v,w] = do
            i <- [1..mw]
            let val = if i < w 
                        then fromMaybe 0 (lookup i xs)
                        else let v1 = fromMaybe 0 (lookup i xs)
                                 v2 = v + fromMaybe 0 (lookup (i-w) xs)
                              in max v1 v2
            return (i,val)