F - Sweet Alchemy Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 900900

問題文

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

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

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

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

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

制約

  • 2N502 ≤ N ≤ 50
  • 1X1091 ≤ X ≤ 10^9
  • 0D1090 ≤ D ≤ 10^9
  • 1mi1091 ≤ m_i ≤ 10^9 (1iN)(1 ≤ i ≤ N)
  • 1pi<i1 ≤ p_i < i (2iN)(2 ≤ i ≤ N)
  • 入力中の値はすべて整数である。

入力

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

NN XX DD
m1m_1
m2m_2 p2p_2
::
mNm_N pNp_N

出力

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


入力例 1Copy

Copy
3 100 1
15
10 1
20 1

出力例 1Copy

Copy
7

100100 グラムのお菓子の素があり、赤木さんは 33 種類のドーナツを作ることができ、守るべき条件は c1c2c1+1c_1 ≤ c_2 ≤ c_1 + 1c1c3c1+1c_1 ≤ c_3 ≤ c_1 + 1 です。ドーナツ 1122 個、ドーナツ 2233 個、ドーナツ 3322 個作るのが最適です。


入力例 2Copy

Copy
3 100 10
15
10 1
20 1

出力例 2Copy

Copy
10

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


入力例 3Copy

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

出力例 3Copy

Copy
7496296

Score : 900900 points

Problem Statement

Akaki, a patissier, can make NN kinds of doughnut using only a certain powder called "Okashi no Moto" (literally "material of pastry", simply called Moto below) as ingredient. These doughnuts are called Doughnut 11, Doughnut 22, ...,..., Doughnut NN. In order to make one Doughnut ii (1iN)(1 ≤ i ≤ N), she needs to consume mim_i grams of Moto. She cannot make a non-integer number of doughnuts, such as 0.50.5 doughnuts.

The recipes of these doughnuts are developed by repeated modifications from the recipe of Doughnut 11. Specifically, the recipe of Doughnut ii (2iN)(2 ≤ i ≤ N) is a direct modification of the recipe of Doughnut pip_i (1pi<i)(1 ≤ p_i < i).

Now, she has XX grams of Moto. She decides to make as many doughnuts as possible for a party tonight. However, since the tastes of the guests differ, she will obey the following condition:

  • Let cic_i be the number of Doughnut ii (1iN)(1 ≤ i ≤ N) that she makes. For each integer ii such that 2iN2 ≤ i ≤ N, cpicicpi+Dc_{p_i} ≤ c_i ≤ c_{p_i} + D must hold. Here, DD is a predetermined value.

At most how many doughnuts can be made here? She does not necessarily need to consume all of her Moto.

Constraints

  • 2N502 ≤ N ≤ 50
  • 1X1091 ≤ X ≤ 10^9
  • 0D1090 ≤ D ≤ 10^9
  • 1mi1091 ≤ m_i ≤ 10^9 (1iN)(1 ≤ i ≤ N)
  • 1pi<i1 ≤ p_i < i (2iN)(2 ≤ i ≤ N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN XX DD
m1m_1
m2m_2 p2p_2
::
mNm_N pNp_N

Output

Print the maximum number of doughnuts that can be made under the condition.


Sample Input 1Copy

Copy
3 100 1
15
10 1
20 1

Sample Output 1Copy

Copy
7

She has 100100 grams of Moto, can make three kinds of doughnuts, and the conditions that must hold are c1c2c1+1c_1 ≤ c_2 ≤ c_1 + 1 and c1c3c1+1c_1 ≤ c_3 ≤ c_1 + 1. It is optimal to make two Doughnuts 11, three Doughnuts 22 and two Doughnuts 33.


Sample Input 2Copy

Copy
3 100 10
15
10 1
20 1

Sample Output 2Copy

Copy
10

The amount of Moto and the recipes of the doughnuts are not changed from Sample Input 1, but the last conditions are relaxed. In this case, it is optimal to make just ten Doughnuts 22. As seen here, she does not necessarily need to make all kinds of doughnuts.


Sample Input 3Copy

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

Sample Output 3Copy

Copy
7496296


2025-05-04 (Sun)
00:38:05 +00:00