← 返回题目列表

AtCoder · arc096_d

F. 甜蜜炼金术

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

Akaki,一名糕点师,可以制作 N 仅使用一种名为“Okashi no Moto”(字面意思是“糕点材料”,以下简称为Moto)的粉末作为成分的甜甜圈。这些甜甜圈被称为甜甜圈 1, 甜甜圈 2, ..., 甜甜圈 N。为了制作一个甜甜圈 i (1 ≤ i ≤ N),她需要消耗 m_i 克摩托。她不能制作非整数个甜甜圈,例如 0.5 甜甜圈。

这些甜甜圈的配方是根据甜甜圈的配方反复修改而开发的 1。具体来说,甜甜圈的食谱 i (2 ≤ i ≤ N) 是直接修改Donut的配方 p_i (1 ≤ p_i < i).

现在,她已经 X 克摩托。她决定为今晚的聚会制作尽可能多的甜甜圈。但由于客人的口味不同,她会遵守以下条件:

  • 让 c_i 是甜甜圈的数量 她制作的 i (1 ≤ i ≤ N) 。对于每个整数 i 这样 2 ≤ i ≤ N, c_{p_i} ≤ c_i ≤ c_{p_i} + D 必须保留。在这里, D 是预定值。

这里最多可以制作多少个甜甜圈?她不一定需要消耗掉她所有的摩托。

约束

  • 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)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N X D
m_1
m_2 p_2
:
m_N p_N

输出

打印在该条件下可以制作的甜甜圈的最大数量。


示例输入 1

3 100 1
15
10 1
20 1

示例输出 1

7

她有 100 克Moto,可以制作三种甜甜圈,必须满足的条件是 c_1 ≤ c_2 ≤ c_1 + 1 和 c_1 ≤ c_3 ≤ c_1 + 1。最好做两个甜甜圈 1,三个甜甜圈 2 和两个甜甜圈 3.


示例输入 2

3 100 10
15
10 1
20 1

示例输出 2

10

Moto 的数量和甜甜圈的配方与示例输入 1 相比没有变化,但最后的条件放宽了。在这种情况下,最好只制作十个甜甜圈 2。从这里可以看出,她不一定需要制作各种甜甜圈。


示例输入 3

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

示例输出 3

7496296