{-
問題文
N個の品物があります。品物には 1,2,…,N と番号が振られています。
各 i (1≤i≤N) について、品物 i の重さは wi で、価値は viです。

太郎君は、N個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。
ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約
入力はすべて整数である。
    1≤N≤100
    1≤W≤10^5
    1≤wi≤W
    1≤vi≤10^9

入力
入力は以下の形式で標準入力から与えられる。
    N W
    w1 v1
    w2 v2
    :
    wN vN

出力
太郎君が持ち帰る品物の価値の総和の最大値を出力せよ。
-}

import Control.Monad
import Control.Monad.ST
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Array
import Data.Array.ST

main = do
    [n,w]<-map read.words<$>getLine::IO [Int]
    wvs<-replicateM n $ unfoldr (B.readInt.B.dropWhile(==' '))<$>B.getLine::IO[[Int]]
    print $ f n w wvs

f n w wvs = runST $ do
    dp <- newArray ((0,0),(n,w)) 0 :: ST s (STUArray s (Int,Int) Int)
    forM_ [(i,wi,vi,j)|(i,[wi,vi])<-zip [1..] wvs,j<-[0..w]] $ \(i,wi,vi,j) ->
        if j<wi then
            writeArray dp (i,j) =<< readArray dp (i-1,j)
        else 
            writeArray dp (i,j) =<< maximum <$> sequence [readArray dp (i-1,j), (+vi)<$>readArray dp (i-1,j-wi)]
    readArray dp (n,w)
