open System.Collections.Generic

let [|N;W|] = stdin.ReadLine().Split() |> Array.map int
let wv =
    [|1..N|]
    |> Array.map (fun _ -> stdin.ReadLine().Split() |> Array.map int)

let g i w =
    let cache = Dictionary()
    let rec f id wt =
        if id=0 then
            if wt>=wv.[0].[0] then
                int64(wv.[0].[1])
            else 0L
        else
            let value = ref 0L
            let exist = cache.TryGetValue ((id,wt),value)
            if exist then !value
            else
                if wt >= wv.[id].[0] then
                    let value = max (f (id-1) (wt-wv.[id].[0]) + int64(wv.[id].[1])) (f (id-1) wt)
                    cache.Add ((id,wt),value)
                    value
                else
                    let value = f (id-1) wt
                    cache.Add ((id,wt),value)
                    value
    f i w

g (N-1) W |> stdout.WriteLine