let table = Hashtbl.create ~random:false 10000

let main () =
  let n, w = Scanf.scanf "%d %d\n" (fun a b -> a, b) in
  let xs = Array.make n (0, 0) in
  for i = 0 to n - 1 do
    xs.(i) <- Scanf.scanf "%d %d\n" (fun a b -> a, b)
  done;
  let rec func (i, w) = (
    if i = 0 then 0 else
    if Hashtbl.mem table (i, w) then Hashtbl.find table (i, w) else
      let (v, weight) = xs.(i) in
      if w > weight then (Hashtbl.add table (i, w) (func (i - 1, w)); func (i - 1, w)) else (
        let ans = max (func (i, w - weight) + v) (func (i - 1, w)) in
        Hashtbl.add table (i, w) ans;
        ans
      )
  ) in
  Printf.printf "%d\n" @@ func (n, w)

let _ = main ()

