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

let solve a n w =
  let s = Array.make (w + 1) 0 in
  let t = Array.copy s in
  for i = 1 to n do
    for j = a.(i-1).w to w do
      t.(j) <-
        if s.(j) >= s.(j - a.(i-1).w) + a.(i-1).v
        then s.(j)
        else s.(j - a.(i-1).w) + a.(i-1).v;
    done;
    Array.iteri (fun i e -> s.(i) <- e) t;
  done;
  t.(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"