P10759 [BalticOI 2024] Jobs

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

Currently, you can choose from $N$ one-time jobs numbered from $1$ to $N$. Completing job $i$ will bring you a profit of $x$ euros, and of course, the profit may also be negative. Some jobs depend on another job. That is, there may be a job with index $p$ that must be completed before job $i$ can be started. Therefore, if a high-profit job depends on a job with negative profit, the overall gain may look smaller. If $p = 0$, then job $i$ has no dependency. You currently have $s$ euros. You can decide which jobs to do and in what order, as long as you respect the dependencies. In addition, the amount of money you have must never become negative at any time. Please compute the maximum profit you can obtain by choosing and completing these $N$ jobs in some order (and possibly leaving some jobs undone)。

The first line contains two integers $N$ and $s$, representing the number of jobs and the amount of money you initially have. The next $N$ lines each contain two integers $x$ and $p$, representing the profit of job $i$ and the index of its prerequisite job. If $p = 0$, then job $i$ has no dependency。

Your program should output a single integer: the maximum profit you can obtain。

Choose jobs $1,4,3,5$ respectively, and the total profit is $3+2-5+6 = 6$. | Subtask ID | Special Property | Score | | :-----------: | :-----------: | :-----------: | | $1$ | $s = 10^{18}$ | $11$ | | $2$ | $N \leq 2000$ and satisfies Property A | $14$ | | $3$ | Satisfies Property A | $15$ | | $4$ | $N \leq 2000$ | $29$ | | $5$ | No special property | $31$ | * Property A: each $p_i$ is either $0$ or $i-1$. For all testdata, $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$. Translated by ChatGPT 5