问题描述

Akaki是一名糕点师傅，她只能使用一种叫做"Okashi no Moto"的粉末来制作$N$种甜甜圈。这些甜甜圈被称为甜甜圈$1$、甜甜圈$2$、...、甜甜圈$N$。为了制作一个甜甜圈$i$ $(1 ≤ i ≤ N)$，她需要消耗$m_i$克的"Okashi no Moto"。她无法制作非整数数量的甜甜圈，比如$0.5$个甜甜圈。

这些甜甜圈的配方是通过对甜甜圈$1$的配方进行反复修改得到的。具体而言，甜甜圈$i$ $(2 ≤ i ≤ N)$的配方是甜甜圈$p_i$ $(1 ≤ p_i < i)$配方的直接修改。

现在，她有$X$克的"Okashi no Moto"。她决定尽可能多地制作甜甜圈参加今晚的派对。然而，由于客人们的口味不同，她必须遵守以下条件：

• 让$c_i$表示她制作的甜甜圈$i$ $(1 ≤ i ≤ N)$的数量。对于每个整数$i$满足$2 ≤ i ≤ N$，必须满足$c_{p_i} ≤ c_i ≤ c_{p_i} + D$。其中，$D$是预先确定的值。

最多可以制作多少个甜甜圈？她不一定需要消耗掉所有的"Okashi no Moto"。

约束条件

• $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)$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入获得：

$N$ $X$ $D$ $m_1$ $m_2$ $p_2$ $:$ $m_N$ $p_N$

输出

打印在给定条件下能够制作的甜甜圈的最大数量。

示例输入1

3 100 1
15
10 1
20 1

示例输出1

7

她有$100$克的"Okashi no Moto"，可以制作三种甜甜圈，并且必须满足的条件是$c_1 ≤ c_2 ≤ c_1 + 1$和$c_1 ≤ c_3 ≤ c_1 + 1$。最佳方案是制作两个甜甜圈$1$、三个甜甜圈$2$和两个甜甜圈$3$。

示例输入2

3 100 10
15
10 1
20 1

示例输出2

10

"Okashi no Moto"的数量和甜甜圈的配方与示例输入1相同，但最后的条件放宽了。在这种情况下，最佳方案是制作十个甜甜圈$2$。正如这里所示，她不一定需要制作所有种类的甜甜圈。

示例输入3

5 1000000000 1000000
123
159 1
111 1
135 3
147 3

示例输出3

7496296