题目描述

パティシエの赤木さんは、「お菓子の素」という粉のみを材料として $N$ 種類のドーナツを作ることができます。これらのドーナツはドーナツ $1$、ドーナツ $2$、$...$、ドーナツ $N$ と呼ばれます。ドーナツ $i$ $(1\ <\ =\ i\ <\ =\ N)$ を $1$ 個作るには、お菓子の素 $m_i$ グラムを消費する必要があります。なお、$0.5$ 個など整数でない個数のドーナツを作ることはできません。

これらのドーナツのレシピは、ドーナツ $1$ のレシピから改変を繰り返して開発されたものです。 具体的には、ドーナツ $i$ $(2\ <\ =\ i\ <\ =\ N)$ のレシピはドーナツ $p_i$ $(1\ <\ =\ p_i\ <\ i)$ のレシピを直接改変したものです。

いま、赤木さんはお菓子の素を $X$ グラム持っています。これを使って、今夜のパーティーに向けて可能な限りたくさんのドーナツを作ることにしました。ただし、来客の好みは様々なので、次の条件を守ることにしました。

• ドーナツ $i$ $(1\ <\ =\ i\ <\ =\ N)$ を作る個数を $c_i$ とする。$2\ <\ =\ i\ <\ =\ N$ であるようなどの整数 $i$ に対しても、$c_{p_i}\ <\ =\ c_i\ <\ =\ c_{p_i}\ +\ D$ となるように作る。ここで、$D$ はあらかじめ決まった値である。

このとき、最大で何個のドーナツを作ることができるでしょうか？お菓子の素を使い切る必要はありません。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件を守って作ることのできるドーナツの最大の個数を出力せよ。

题目大意

有 $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\le n \le 50,\ 1\le x,m_i\le 10^9,\ 0\le d \le 10^9, 1\le p_i < i$

3 100 1
15
10 1
20 1

7

3 100 10
15
10 1
20 1

10

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

7496296

提示

制約

• $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)$
• 入力中の値はすべて整数である。

Sample Explanation 1

$100$ グラムのお菓子の素があり、赤木さんは $3$ 種類のドーナツを作ることができ、守るべき条件は $c_1\ <\ =\ c_2\ <\ =\ c_1\ +\ 1$、$c_1\ <\ =\ c_3\ <\ =\ c_1\ +\ 1$ です。ドーナツ $1$ を $2$ 個、ドーナツ $2$ を $3$ 個、ドーナツ $3$ を $2$ 個作るのが最適です。

Sample Explanation 2

入力例 1 からお菓子の素の量やドーナツのレシピそのものは変わっていませんが、最後の条件が緩くなっています。この場合、ドーナツ $2$ だけを $10$ 個作るのが最適です。このように、必ずしもすべての種類のドーナツを作らなくても構いません。