[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 $ はあらかじめ決まった値である。このとき、最大で何個のドーナツを作ることができるでしょうか？お菓子の素を使い切る必要はありません。

AT_arc096_d [ARC096F] Sweet Alchemy

Description

Input Format

Output Format

Explanation/Hint