let rec floor_sqrt acc acc_x_2_x_r sq_acc_minus_z r sq_r =
  if r = 0 then acc
  else
    let sq_acc_minus_z' = sq_acc_minus_z + acc_x_2_x_r + sq_r in
    ( if sq_acc_minus_z' <= 0 then
        floor_sqrt (acc + r) ((acc_x_2_x_r lsr 1) + sq_r) sq_acc_minus_z'
      else
        floor_sqrt acc (acc_x_2_x_r lsr 1) sq_acc_minus_z) (r lsr 1) (sq_r lsr 2)
let floor_sqrt z = floor_sqrt 0 0 (~-z) (1 lsl 30) (1 lsl 60)

let () = Scanf.scanf "%d\n" @@ fun n ->
  let vs = Array.make n 0 in
  let ws = Array.make n 0 in
  for i = 0 to n - 1 do
    Scanf.scanf "%d %d\n" @@ fun v w ->
      vs.(i) <- v;
      ws.(i) <- w
  done;
  Scanf.scanf "%d\n" @@ fun q ->
    let vls = Array.init q @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun v l -> v, l in
    let maxl = Array.fold_right (fun (_, l) -> max l) vls min_int in
    let n' = floor_sqrt n in
    let dp = Bigarray.Array2.create Bigarray.int Bigarray.c_layout (n' + 1) (maxl + 1) in
    Bigarray.Array2.fill (Bigarray.Array2.sub_left dp 0 1) 0;
    for i = 1 to n' do
      let v = Array.unsafe_get vs (i - 1) in
      let w = Array.unsafe_get ws (i - 1) in
      Bigarray.Array2.blit
        (Bigarray.Array2.sub_left dp (i lsr 1) 1)
        (Bigarray.Array2.sub_left dp i 1);
      for j = w to maxl do
        let d = Bigarray.Array2.unsafe_get dp (i lsr 1) j in
        let d' = v + Bigarray.Array2.unsafe_get dp (i lsr 1) (j - w) in
        if d < d' then Bigarray.Array2.unsafe_set dp i j d'
      done
    done;
    let rec solve l i s m =
      if l < 0
      then m
      else if i <= n'
      then max m (s + Bigarray.Array2.unsafe_get dp i l)
      else solve l (i lsr 1) s @@ solve (l - Array.unsafe_get ws (i - 1)) (i lsr 1) (s + Array.unsafe_get vs (i - 1)) m in
    Array.iter (fun (v, l) -> Printf.printf "%d\n" @@ solve l v 0 min_int) vls

