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 vws = Array.init n @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun v w -> v, w in
  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 = Array.make_matrix (n' + 1) (maxl + 1) 0 in
    for i = 1 to n' do
      let v, w = vws.(i - 1) in
      for j = 0 to w - 1 do
        dp.(i).(j) <- dp.(i lsr 1).(j)
      done;
      for j = w to maxl do
        dp.(i).(j) <- max dp.(i lsr 1).(j) (v + dp.(i lsr 1).(j - w))
      done
    done;
    let rec solve l i s m =
      let v, w = vws.(i - 1) in
      if l < 0
      then m
      else if i <= n'
      then max m (s + dp.(i).(l))
      else solve l (i lsr 1) s @@ solve (l - w) (i lsr 1) (s + v) m in
    Array.iter (fun (v, l) -> Printf.printf "%d\n" @@ solve l v 0 min_int) vls

