分数: 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