output_description: For each integer i from 1 through Q, the i-th line should contain the response
  to the i-th query.
  
  * * *
input_description: Let v_i and L_i be the values v and L given in the i-th query. Then, Input is
  given from Standard Input in the following format:
  
      
      
      N
      V_1 W_1
      :
      V_N W_N
      Q
      v_1 L_1
      :
      v_Q L_Q
attempt: def main():
      from sys import stdin
  
      input = stdin.readline
  
      n = int(input())
      vw = [list(map(int, input().split())) for _ in [0] * n]
      q = int(input())
      vl = [list(map(int, input().split())) for _ in [0] * q]
  
      former = min(512, n)
      former_dp = [[-1] * 100001 for _ in [0] * former]
      former_set = [set() for _ in [0] * former]
  
      former_dp[0][0] = 0
      former_dp[0][vw[0][1]] = vw[0][0]
      former_set[0] = {0, vw[0][1]}
  
      for i in range(1, former):
          v, w = vw[i]
          anc_dp = former_dp[(i - 1) // 2]
          now_dp = former_dp[i]
          anc_set = former_set[(i - 1) // 2]
          now_set = former_set[i]
          for j in anc_set:
              now_dp[j] = anc_dp[j]
              now_set.add(j)
          for j in anc_set:
              if w + j <= 100000:
                  now_dp[w + j] = max(now_dp[w + j], anc_dp[j] + v)
                  now_set.add(w + j)
  
      for i in range(former):
          m = 0
          now_dp = former_dp[i]
          for j in range(1, 100001):
              m = max(m, now_dp[j])
              now_dp[j] = m
  
      for v, l in vl:
          if v <= former:
              print(former_dp[v - 1][l])
              continue
          later = []
          vv = v
          while vv > former:
              later.append(vw[vv - 1])
              vv >>= 1
          anc_dp = former_dp[vv - 1]
          m = len(later)
          ans = 0
  
          print(ans)
  
  
  main()
  
problem_description: Statement
  
  We have a rooted binary tree with N vertices, where the vertices are numbered
  1 to N. Vertex 1 is the root, and the parent of Vertex i (i \geq 2) is Vertex
  \left[ \frac{i}{2} \right].
  
  Each vertex has one item in it. The item in Vertex i has a value of V_i and a
  weight of W_i. Now, process the following query Q times:
  
    * Given are a vertex v of the tree and a positive integer L. Let us choose some (possibly none) of the items in v and the ancestors of v so that their total weight is at most L. Find the maximum possible total value of the chosen items.
  
  Here, Vertex u is said to be an ancestor of Vertex v when u is an indirect
  parent of v, that is, there exists a sequence of vertices w_1,w_2,\ldots,w_k
  (k\geq 2) where w_1=v, w_k=u, and w_{i+1} is the parent of w_i for each i.
samples: [{"input": "3\n    1 2\n    2 3\n    3 4\n    3\n    1 1\n    2 5\n    3 5", "output": "0\n    3\n    3\n    \n\nIn the first query, we are given only one choice: the item with (V, W)=(1,2).\nSince L = 1, we cannot actually choose it, so our response should be 0.\n\nIn the second query, we are given two choices: the items with (V, W)=(1,2) and\n(V, W)=(2,3). Since L = 5, we can choose both of them, so our response should\nbe 3.\n\n* * *"}, {"input": "15\n    123 119\n    129 120\n    132 112\n    126 109\n    118 103\n    115 109\n    102 100\n    130 120\n    105 105\n    132 115\n    104 102\n    107 107\n    127 116\n    121 104\n    121 115\n    8\n    8 234\n    9 244\n    10 226\n    11 227\n    12 240\n    13 237\n    14 206\n    15 227", "output": "256\n    255\n    250\n    247\n    255\n    259\n    223\n    253"}]