let solve n w d =
  let t = Array.make_matrix (n + 1) (w + 1) 0 in
  let rec doit = function
    | (i, _) when i > n -> t.(n).(w)
    | (i, x) when x > w -> doit (i + 1, 1)
    | (i, x) ->
      let (vi, wi) = d.(i-1) in
      t.(i).(x) <-
        if wi <= x && t.(i-1).(x-wi) + vi > t.(i-1).(x) then t.(i-1).(x-wi) + vi
        else t.(i-1).(x);
      doit (i, x + 1) in
  doit (1, 1)

let read () = Scanf.scanf "%d %d\n" (fun x y -> (x, y))

let () =
  let (n, w) = read () in
  let d = Array.init n (fun _ -> read ()) in
  Printf.printf "%d\n" (solve n w d)