[ARC096F] Sweet Alchemy

有 $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$

[problemUrl]: https://atcoder.jp/contests/arc096/tasks/arc096_d パティシエの赤木さんは、「お菓子の素」という粉のみを材料として $ 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 $

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

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 $ 個作るのが最適です。このように、必ずしもすべての種類のドーナツを作らなくても構いません。