配点 : $900$ 点

問題文

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

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

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

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

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

制約

• $2 \leq N \leq 50$
• $1 \leq X \leq 10^9$
• $0 \leq D \leq 10^9$
• $1 \leq m_i \leq 10^9$ $(1 \leq i \leq N)$
• $1 \leq p_i < i$ $(2 \leq i \leq N)$
• 入力中の値はすべて整数である。

入力

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

$N$ $X$ $D$

$m_1$

$m_2$ $p_2$

$:$

$m_N$ $p_N$

出力

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

3 100 1
15
10 1
20 1

7

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

3 100 10
15
10 1
20 1

10

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

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

7496296