[<AutoOpen>]
module Program

open System

let read f = stdin.ReadLine() |> f
let reada f = stdin.ReadLine().Split() |> Array.map f
let reads f = stdin.ReadLine().Split() |> Array.toList |> List.map f

[<EntryPoint>]
let main _ =
    let [n;w] = reads int
    let wvs = Array.init n (fun _ -> reads int)

    let dp = Array2D.create (n + 1) (w + 1) 0L
    for i = 1 to n do
        let [iw;iv] = wvs.[i-1]
        for j = 0 to w do
            if j - iw >= 0 then
                dp.[i, j] <- max (dp.[i-1, j]) (dp.[i-1, j-iw] + int64 iv)
            else
                dp.[i, j] <- dp.[i-1, j]

    printfn "%i" dp.[n, w]
    0