let n, w = Scanf.scanf " %d %d" @@ fun a b -> a, b
let wvs = Array.init n @@ fun _ -> Scanf.scanf " %d %d" @@ fun a b -> a, b
let dp = Array.make_matrix n (w + 1) 0
let _ =
  for i = 0 to w do let (w', v) = wvs.(0) in if w' <= i then dp.(0).(i) <- v done;
  for i = 1 to n - 1 do
    for j = 0 to w do
      dp.(i).(j) <- dp.(i - 1).(j);
      let w', v = wvs.(i) in
      if w' <= j then dp.(i).(j) <- max dp.(i).(j) @@ dp.(i - 1).(j - w') + v done done;
  Printf.printf "%d\n" @@ dp.(n - 1).(w)