题目描述

题目译自 BalticOI 2024 Day1「Jobs」

你拥有一家通过为客户完成工作来赚钱的企业。目前，你可以从 $N$ 个一次性工作中进行选择，编号从 $1$ 到 $N$。

完成第 $i$ 个工作会带来 $x_i$ 欧元的利润。利润也可能为负数（$x_i < 0$）。

有些工作依赖于另一个工作。也就是说，可能存在一个编号为 $p_i$ 的工作必须先完成，然后才能开始第 $i$ 个工作。因此，一个利润很高的工作如果它依赖于一个利润为负的工作，就可能比看起来的吸引力小。如果 $p_i = 0$，第 $i$ 个工作没有任何依赖关系。

你目前拥有 $s$ 欧元。只要满足依赖关系，你可以决定完成哪些工作以及按什么顺序完成它们。此外，你拥有的钱数在任何时候都不能变为负数。

请计算通过选择完成部分（可能没有）$N$ 个工作并按选定的顺序完成，可以获得的最大利润。

输入格式

第一行两个整数 $N$ 和 $s$，分别表示工作数和你最初拥有的钱数。

接下来 $N$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $p_i$，分别表示利润和完成工作 $i$ 之前需要完成的工作编号。如果 $p_i=0$，则表示工作 $i$ 没有工作依赖。

输出格式

输出一个整数，表示你能获得的最大利润。

6 1
3 0
-3 1
-5 0
2 1
6 3
-4 5

6

数据范围与提示

对于所有数据，满足：

• $1\le N\le 3\cdot 10^5$
• $0\le s\le 10^{18}$
• $-10^9\le x_i\le 10^9$（对于所有 $1\le i\le N$）
• $0\le p_i<i$（对于所有 $1\le i\le N$）

详细子任务附加限制及分值如下表所示。