program knapsack_queries_on_a_tree
  implicit none
  integer, parameter :: m = 511
  integer :: n, q, u, l, i, j, k
  integer, dimension(2 ** 18 - 1) :: v = 0, w = 0
  integer(8) :: dp(0:m, 0:100000) = 0
  read(*,*) n
  do i = 1, n
    read(*,*) v(i), w(i)
  end do
  do i = 1, m
    k = i / 2
    do j = 1, 100000
      dp(i, j) = max(dp(k, j), merge(0_8, dp(k, j - w(i)) + v(i), j < w(i)))
    end do
  end do
  read(*,*) q
  do i = 1, q
    read(*,*) u, l
    write(*,'(i0)') query(u, l)
  end do
contains
  recursive integer(8) function query(i, j) result(res)
    integer, intent(in) :: i, j
    integer :: k
    if (i <= m) then
      res = dp(i, j)
      return
    end if
    k = i / 2
    res = max(query(k, j), merge(0_8, query(k, j - w(i)) + v(i), j < w(i)))
  end
end program knapsack_queries_on_a_tree