program knapsack_queries_on_a_tree
  implicit none
  integer :: n, q, u, l, i, j, k
  integer, allocatable :: w(:)
  integer(8), allocatable :: v(:), dp(:, :)
  read(*,*) n
  allocate(v(n), w(n), dp(512, 0:100000))
  do i = 1, n
    read(*,*) v(i), w(i)
  end do
  dp = 0
  do i = 2, 512
    k = i / 2
    do j = 1, 100000
      dp(i, j) = dp(k, j)
      if (j >= w(i)) dp(i, j) = max(dp(i, j), dp(k, j - w(i)) + v(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
    if (i <= 512) then
      res = dp(i, j)
      return
    end if
    res = query(i / 2, j)
    if (j >= w(i)) res = max(res, query(i / 2, j - w(i)) + v(i))
  end
end program knapsack_queries_on_a_tree