P10759 [BalticOI 2024] Jobs

翻译自 [BalticOI 2024 Day1 T1](https://boi2024.lmio.lt/tasks/d1-jobs-statement.pdf)。

目前，你可以选择从 $1$ 到 $N$ 编号的 $N$ 个一次性工作。 完成第 $i$ 个工作将给你带来 $x$ 欧元的利润，当然，利润也可能是负的。 有些工作依赖于另一个工作。也就是说，可能有一个编号为 $p$ 的工作必须在第 $i$ 个工作开始之前完成。因此，一个利润较大的工作如果依赖于一个利润为负的工作，看起来收益可能会比较小。 如果 $p = 0$，则第 $i$ 个工作没有依赖。 你目前有 $s$ 欧元，可以决定做哪些工作以及以什么顺序去做，只要尊重依赖关系。此外，你所拥有的钱数在任何时候都不能变成负数。 请计算通过选择按照某种顺序完成（也可能某些选择不完成）这 $N$ 个工作所能获得的最大利润。

第一行包含两个整数 $N$ 和 $s$，分别是工作的数量和你最初拥有的金额。 接下来的 $N$ 行，每行包含两个整数 $x$ 和 $p$，分别是第 $i$ 个工作的利润和它所依赖的前置工作的编号。如果 $p = 0$，则第 $i$ 个工作没有依赖。

你的程序应该输出一个整数，即你能够获得的最大利润。

分别选择 $1,4,3,5$ 号工作即可，总利润为 $3+2-5+6 = 6$。 | 子任务编号 | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | | $1$ | $s = 10^{18}$ | $11$ | | $2$ | $N \leq 2000$ 且满足性质 A | $14$ | | $3$ | 满足性质 A | $15$ | | $4$ | $N \leq 2000$ | $29$ | | $5$ | 无特殊性质 | $31$ | * 性质 A：每个 $p_i$ 要么是 $0$，要么是 $i-1$。 对于所有的数据，$1 \leq N \leq 3 \times 10^5$，$0 \leq s \leq 10^{18}$，$-10^9 \leq x_i \leq 10^9$，$0 \leq p_i < i$。