#P13720. [ARC096F] Sweet Alchemy

    ID: 12922 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-差分转化多重背包排序贪心交换论证以值为状态二进制拆分倒序更新避免重复使用

[ARC096F] Sweet Alchemy

题目描述

有 nn 个物品和 xx 个特殊材料,制作第 ii 个物品需要 mim_i 个特殊材料。给出一个整数 dd,对于每个 i  (2≤i≤n)i\ \ (2\le i\le n) 给定 pi  (1≤pi<i)p_i\ \ (1\le p_i<i),设在材料充足的情况下制作第 ii 个物品的个数为 cic_i,需满足 cpi≤ci≤cpi+dc_{p_i}\le c_i \le c_{p_i}+d 。最大化制作的物品数。

输入格式

第一行有三个整数:n,x,dn,x,d 。

接下来一行有一个整数表示 m1m_1。

最后 n−1n-1 行每行有两个整数,分别表示 mim_i 和 pip_i 。

输出格式

仅输出一行,表示在满足条件的情况下可以制作的最多物品数。

输入输出样例 #1

输入 #1

3 100 1
15
10 1
20 1

输出 #1

7

输入输出样例 #2

输入 #2

3 100 10
15
10 1
20 1

输出 #2

10

输入输出样例 #3

输入 #3

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

输出 #3

7496296

说明/提示

$1\le n \le 50,\ 1\le x,m_i\le 10^9,\ 0\le d \le 10^9, 1\le p_i < i$