output_description: Print the smallest initial amount of money W that enables you to win the game.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      A_1 B_1
      A_2 B_2
      :
      A_N B_N
      U_1 V_1
      U_2 V_2
      :
      U_M V_M
attempt: import sys, random, time, bisect
  
  input = sys.stdin.buffer.readline
  
  start = time.time()
  N = int(input())
  vw = [(-1, -1)]
  for i in range(N):
      vw.append(tuple(map(int, input().split())))
  
  dp = [[] for i in range(2**9)]
  
  
  def make_dp(v):
      t = [[0, 0] for i in range(15)]
      V = v
      id = 0
      while v >= 1:
          t[id] = vw[v]
          id += 1
          v //= 2
      n = id
      temp = [[0, 0] for i in range(2**n)]
      for i in range(n):
          for j in range(2**i, 2 ** (i + 1)):
              temp[j][0] = temp[j - 2**i][0] + t[i][0]
              temp[j][1] = temp[j - 2**i][1] + t[i][1]
      temp.sort(key=lambda x: x[1])
      for i in range(1, 2**n):
          temp[i][0] = max(temp[i][0], temp[i - 1][0])
  
      dp[V] = [0] * (10**5 + 1)
      for i in range(2**n - 1):
          L = temp[i][1]
          R = temp[i + 1][1]
          if L > 10**5:
              break
          elif R > 10**5:
              R = 10**5 + 1
          for j in range(L, R):
              dp[V][j] = temp[i][0]
      else:
          L = temp[-1][1]
          if L <= 10**5:
              for j in range(L, 10**5 + 1):
                  dp[V][j] = temp[-1][0]
  
  
  MAX = min(2**9, N + 1)
  for i in range(1, MAX):
      make_dp(i)
  
  Q = int(input())
  query = [[] for i in range(N + 1)]
  for i in range(Q):
      v, L = map(int, input().split())
      query[v].append((L, i))
  
  ans = [0] * Q
  temp = [[0, 0] for i in range(2**9)]
  solved = [False] * (N + 1)
  
  
  def solve(v):
      subq = []
      t = []
      check = []
      id = 0
      while v >= 2**9:
          t.append(vw[v])
          subq.append(v)
          check.append(id)
          id += 1
          v //= 2
      if not subq:
          subq = [v]
          check = [0]
  
      t = t[::-1]
      n = len(t)
      for i in range(n):
          for j in range(2**i, 2 ** (i + 1)):
              temp[j][0] = temp[j - 2**i][0] + t[i][0]
              temp[j][1] = temp[j - 2**i][1] + t[i][1]
  
      for i in range(len(check)):
          V = subq[i]
          if not solved[V]:
              solved[V] = True
              for L, ID in query[V]:
                  res = 0
                  m = n - check[i]
                  for i in range(2**m):
                      if L >= temp[i][1]:
                          res = max(res, temp[i][0] + dp[v][L - temp[i][1]])
                  ans[ID] = res
  
  
  for i in range(1, N + 1):
      if query[i] and not solved[i]:
          solve(i)
  
  for i in range(Q):
      print(ans[i])
  
problem_description: Statement
  
  There is a simple undirected graph with N vertices and M edges. The vertices
  are numbered 1 through N, and the edges are numbered 1 through M. Edge i
  connects Vertex U_i and V_i. Also, Vertex i has two predetermined integers A_i
  and B_i. You will play the following game on this graph.
  
  First, choose one vertex and stand on it, with W yen (the currency of Japan)
  in your pocket. Here, A_s \leq W must hold, where s is the vertex you choose.
  Then, perform the following two kinds of operations any number of times in any
  order:
  
    * Choose one vertex v that is directly connected by an edge to the vertex you are standing on, and move to vertex v. Here, you need to have at least A_v yen in your pocket when you perform this move.
    * Donate B_v yen to the vertex v you are standing on. Here, the amount of money in your pocket must not become less than 0 yen.
  
  You win the game when you donate once to every vertex. Find the smallest
  initial amount of money W that enables you to win the game.
samples: [{"input": "4 5\n    3 1\n    1 2\n    4 1\n    6 2\n    1 2\n    2 3\n    2 4\n    1 4\n    3 4", "output": "6\n    \n\nIf you have 6 yen initially, you can win the game as follows:\n\n  * Stand on Vertex 4. This is possible since you have not less than 6 yen.\n  * Donate 2 yen to Vertex 4. Now you have 4 yen.\n  * Move to Vertex 3. This is possible since you have not less than 4 yen.\n  * Donate 1 yen to Vertex 3. Now you have 3 yen.\n  * Move to Vertex 2. This is possible since you have not less than 1 yen.\n  * Move to Vertex 1. This is possible since you have not less than 3 yen.\n  * Donate 1 yen to Vertex 1. Now you have 2 yen.\n  * Move to Vertex 2. This is possible since you have not less than 1 yen.\n  * Donate 2 yen to Vertex 2. Now you have 0 yen.\n\nIf you have less than 6 yen initially, you cannot win the game. Thus, the\nanswer is 6.\n\n* * *"}, {"input": "5 8\n    6 4\n    15 13\n    15 19\n    15 1\n    20 7\n    1 3\n    1 4\n    1 5\n    2 3\n    2 4\n    2 5\n    3 5\n    4 5", "output": "44\n    \n\n* * *"}, {"input": "9 10\n    131 2\n    98 79\n    242 32\n    231 38\n    382 82\n    224 22\n    140 88\n    209 70\n    164 64\n    6 8\n    1 6\n    1 4\n    1 3\n    4 7\n    4 9\n    3 7\n    3 9\n    5 9\n    2 5", "output": "582"}]