type t = { v : int; w : int }

let solve a n w =
  let dp = Array.make_matrix 2 (w + 1) 0 in
  for i = 1 to n do
    for j = a.(i-1).w to w do
      dp.(1).(j) <-
        if dp.(0).(j - a.(i-1).w) + a.(i-1).v <= dp.(0).(j)
        then dp.(0).(j)
        else dp.(0).(j - a.(i-1).w) + a.(i-1).v;
    done;
    for i = 0 to w do dp.(0).(i) <- dp.(1).(i) done;
  done;
  dp.(1).(w)

let () =
  let (n, w) = Scanf.scanf "%d %d " (fun n w -> n, w) in
  let a = Array.init n (fun _ -> Scanf.scanf "%d %d " (fun v w -> { v; w })) in
  solve a n w |> Printf.printf "%d\n"