let rec drop n ls =
    match ls with
    | x :: xs when n > 0 -> drop (n - 1) xs
    | _ -> ls

let update dp w v =
    let rec update_sub dp dp_w =
        match dp, dp_w with
        | _, [] -> dp
        | x :: dp', x_w :: dp_w' ->
            let m = max x (v + x_w) in
            m :: update_sub dp' dp_w'
        | _, _ -> failwith "failed"
    in update_sub dp (drop w dp)

let rec solve (ws, vs) weight dp =
    match (ws, vs) with
    | (w :: ws', v :: vs') -> solve (ws', vs') weight (update dp w v)
    | _ -> List.hd dp

let () =
    Scanf.scanf "%d %d\n" @@ fun n w ->
        let rec loop n =
            if n = 0 then ([], [])
            else Scanf.scanf "%d %d\n" @@ fun w v ->
                let (ws, vs) = loop (n - 1) in
                (w :: ws, v :: vs)
        in
        let ws, vs = loop n in
        let rec init n =
            if n = 0 then []
            else 0 :: init (n - 1)
        in
        Printf.printf "%d\n" @@ solve (ws, vs) w (init (w + 1))
