Problem 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.

Constraints

• $2 ≤ N ≤ 50$
• $1 ≤ X ≤ 10^9$
• $0 ≤ D ≤ 10^9$
• $1 ≤ m_i ≤ 10^9$ $(1 ≤ i ≤ N)$
• $1 ≤ p_i < i$ $(2 ≤ i ≤ N)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X D
m_1
m_2 p_2
:
m_N p_N

Output

Print the maximum number of doughnuts that can be made under the condition.