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

let add a b =
    if a = max_int || b = max_int then max_int
    else a + b

let update dp w v =
    let rec update_sub dp dp_v =
        match dp, dp_v with
        | x :: dp', x_v :: dp_v' -> min x (add w x_v) :: update_sub dp' dp_v'
        | x :: dp', []         -> min x w :: update_sub dp' []
        | []      , []         -> []
        | _                    -> failwith "failed"
    in update_sub dp (drop v dp)

let find_index p ls =
    let rec find_index_sub n ls =
        match ls with
        | x :: xs ->
            if p x then n
            else find_index_sub (n + 1) xs
        | [] -> failwith "not found"
    in find_index_sub 0 ls

let solve (ws, vs) weight max_v dp =
    let rec solve_sub (ws, vs) dp =
        match (ws, vs) with
        | (w :: ws', v :: vs') -> solve_sub (ws', vs') (update dp w v)
        | _ -> dp
    in max_v - find_index ((>=) weight) (solve_sub (ws, vs) 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 max_int :: init (n - 1)
        in
        let max_v = List.fold_left (+) 0 vs in
        Printf.printf "%d\n" @@ solve (ws, vs) w max_v (init max_v)
