let rec knapsack q vs ws =
  let n = List.length ws in
  let xs = Array.init (n+1) (fun _ -> Array.make (q+1) @@ Lazy.from_val 0) in
  let ks = function
      (0,_) -> 0
    | (_,0) -> 0
    | (i,w) when w >= List.nth ws (i-1) -> max (Lazy.force xs.(i-1).(w)) (Lazy.force xs.(i-1).(w - (List.nth ws (i-1))) + List.nth vs (i-1))
    | (i,w) -> Lazy.force xs.(i-1).(w) in
  for i = 0 to n do
    for j = 0 to q do
      xs.(i).(j) <- Lazy.from_val @@ ks (i,j)
    done;
  done;
  ks (n,q)

let _ =
  let (n, w) = Scanf.scanf "%d %d\n" (fun a b -> (a, b)) in
  let vs = ref [] in
  let ws = ref [] in
  for i = 1 to n do
    vs := Scanf.scanf "%d " (fun a -> a) :: !vs;
    ws := Scanf.scanf "%d\n" (fun a -> a) :: !ws;
  done;
  knapsack w !vs !ws

