{-# LANGUAGE OverloadedStrings #-}
module Main where

import           Data.List
import           Control.Monad
import           Debug.Trace
import qualified Data.ByteString.Char8         as BC
import           Data.Maybe                     ( fromJust )
import qualified Data.Set                      as S
import qualified Data.IntMap.Strict            as IM
import qualified Data.IntMap.Lazy            as IML
import qualified Data.Map.Strict               as M
import qualified Data.Map.Lazy               as ML
import           Data.Char
import qualified Data.Array.IArray as A
import Data.Bits

modN = 1000000007


readTuple2 :: IO (Int, Int)
readTuple2 = do
    [a, b] <- map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine
    return (a, b)

readTuple3 :: IO (Int, Int, Int)
readTuple3 = do
    [a, b, c] <- map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine
    return (a, b, c)

readInt :: IO Int
readInt = fst . fromJust . BC.readInt <$> BC.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

split :: (a -> Bool) -> [a] -> [[a]]
split f [] = []
split f as =
    let (fo, la) = span f as
        las      = case la of
            [] -> []
            xs -> split f $ tail xs
    in  case fo of
            [] -> las
            xs -> xs : las

pow :: Int -> Int -> Int -> Int
pow base 1 modNum = base `mod` modNum
pow base time modNum
    | odd time = let 
        a = pow base (time `div` 2) modNum `mod` modNum
        in
        a * a * base `mod` modNum
    | otherwise = let
        a = pow base (time `div` 2) modNum `mod` modNum
        in
        a * a `mod` modNum

solve :: Int -> Int -> [(Int, Int)] -> Int
solve n w merchs = let
    valMap :: A.Array Int (Int, Int)
    valMap = A.array (1, n) $ zip [1..] merchs
    getWV :: Int -> Int -> Int
    getWV 0 _ = 0
    getWV _ 0 = 0
    getWV w v = let
        (wi, vi) = valMap A.! v
        nochoose = dp A.! (w, v - 1)
        in
            if wi > w then nochoose  else
                max nochoose $ dp A.! (w - wi, v - 1) + vi
    dp :: A.Array (Int, Int) Int
    dp = A.array ((0,0), (w,n)) [((i, v), getWV i v)| i <- [0..w], v <- [0..n]]
    in dp A.! (w, n)


main = do
    (n, w) <- readTuple2
    merchs <- replicateM n readTuple2
    print $ solve n w merchs





