题目描述

有 $n$ 个物品和 $x$ 个特殊材料，制作第 $i$ 个物品需要 $m_i$ 个特殊材料。给出一个整数 $d$，对于每个 $i\ \ (2\le i\le n)$ 给定 $p_i\ \ (1\le p_i<i)$，设在材料充足的情况下制作第 $i$ 个物品的个数为 $c_i$，需满足 $c_{p_i}\le c_i \le c_{p_i}+d$ 。最大化制作的物品数。

输入格式

第一行有三个整数：$n,x,d$ 。

接下来一行有一个整数表示 $m_1$。

最后 $n-1$ 行每行有两个整数，分别表示 $m_i$ 和 $p_i$ 。

输出格式

仅输出一行，表示在满足条件的情况下可以制作的最多物品数。

样例 1

输入

3 100 1
15
10 1
20 1

输出

7

样例 2

输入

3 100 10
15
10 1
20 1

输出

10

样例 3

输入

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

输出

7496296

说明/提示

$1\le n \le 50,\ 1\le x,m\_i\le 10^9,\ 0\le d \le 10^9, 1\le p\_i < i$