output_description: Print the maximum number of doughnuts that can be made under the condition.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N X D
      m_1
      m_2 p_2
      :
      m_N p_N
attempt: #!/usr/bin/env python3
  
  INF = 2 * 10**9
  
  
  def solve(n, x, d, ma, pa):
  
      v = [1] * n
      w = [0] * n
      for i in range(n - 1, -1, -1):
          w[i] += ma[i]
          if 0 <= pa[i]:
              v[pa[i]] += v[i]
              w[pa[i]] += w[i]
  
      if d == 0:
          return (x // w[0]) * n
  
      c_0 = max(0, x - sum(w[1:]) * d + w[0] - 1) // w[0]
      ans = n * c_0
      y = w[0] * c_0
  
      mean_w = [None] * n
      for i in range(n):
          mean_w[i] = (w[i] / v[i], i)
      mean_w.sort()
  
      t = [0] * n
      llj = lj = -1
      for i in range(n):
          _, j = mean_w[i]
          if j == 0:
              t[0] = (x - y) // w[0]
              y += w[0] * t[0]
              lj = 0
              break
          if x <= y + w[j] * d:
              t[j] = (x - y) // w[j]
              y += w[j] * t[j]
              lj = j
              break
          y += w[j] * d
          t[j] = d
          llj = j
  
      c_max = min(n, d)
      if c_max <= t[lj]:
          y -= w[lj] * c_max
          t[lj] -= c_max
      else:
          y -= w[lj] * t[lj]
          t[lj] = 0
          if llj != -1:
              y -= w[llj] * c_max
              t[llj] -= c_max
  
      ans += sum([v[j] * t[j] for j in range(n)])
  
      j_max = c_max * n * n
      v_max = 0
      rx = x - y
  
      dp = [[0] + [INF] * j_max for _ in range(n)]
      for j in range(1, j_max // n + 1):
          dp[0][n * j] = ndp = w[0] * j
          if ndp <= rx:
              v_max = n * j
      for i in range(1, n):
          vi = v[i]
          wi = w[i]
          for j in range(1, j_max + 1):
              ndp = dp[i - 1][j]
              nj = j
              w_sum = 0
              for k in range(1, min(c_max, d - t[i])):
                  nj -= vi
                  w_sum += wi
                  if nj < 0:
                      break
                  ndp = min(ndp, dp[i - 1][nj] + w_sum)
              dp[i][j] = ndp
              if ndp <= rx:
                  if v_max < j:
                      v_max = j
  
      ans += v_max
  
      return ans
  
  
  def main():
      n, x, d = input().split()
      n = int(n)
      x = int(x)
      d = int(d)
      ma = []
      pa = []
      m = input()
      m = int(m)
      ma.append(m)
      pa.append(-1)
      for _ in range(n - 1):
          m, p = input().split()
          m = int(m)
          ma.append(m)
          p = int(p) - 1
          pa.append(p)
  
      print(solve(n, x, d, ma, pa))
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  Akaki, a patissier, can make N kinds of doughnut using only a certain powder
  called "Okashi no Moto" (literally "material of pastry", simply called Moto
  below) as ingredient. These doughnuts are called Doughnut 1, Doughnut 2, ...,
  Doughnut N. In order to make one Doughnut i (1 ≤ i ≤ N), she needs to consume
  m_i grams of Moto. She cannot make a non-integer number of doughnuts, such as
  0.5 doughnuts.
  
  The recipes of these doughnuts are developed by repeated modifications from
  the recipe of Doughnut 1. Specifically, the recipe of Doughnut i (2 ≤ i ≤ N)
  is a direct modification of the recipe of Doughnut p_i (1 ≤ p_i < i).
  
  Now, she has X grams of Moto. She decides to make as many doughnuts as
  possible for a party tonight. However, since the tastes of the guests differ,
  she will obey the following condition:
  
    * Let c_i be the number of Doughnut i (1 ≤ i ≤ N) that she makes. For each integer i such that 2 ≤ i ≤ N, c_{p_i} ≤ c_i ≤ c_{p_i} + D must hold. Here, D is a predetermined value.
  
  At most how many doughnuts can be made here? She does not necessarily need to
  consume all of her Moto.
samples: [{"input": "3 100 1\n    15\n    10 1\n    20 1", "output": "7\n    \n\nShe has 100 grams of Moto, can make three kinds of doughnuts, and the\nconditions that must hold are c_1 \u2264 c_2 \u2264 c_1 + 1 and c_1 \u2264 c_3 \u2264 c_1 + 1. It\nis optimal to make two Doughnuts 1, three Doughnuts 2 and two Doughnuts 3.\n\n* * *"}, {"input": "3 100 10\n    15\n    10 1\n    20 1", "output": "10\n    \n\nThe amount of Moto and the recipes of the doughnuts are not changed from\nSample Input 1, but the last conditions are relaxed. In this case, it is\noptimal to make just ten Doughnuts 2. As seen here, she does not necessarily\nneed to make all kinds of doughnuts.\n\n* * *"}, {"input": "5 1000000000 1000000\n    123\n    159 1\n    111 1\n    135 3\n    147 3", "output": "7496296"}]