Background

Translated from BalticOI 2024 Day1 T1。

Problem Description

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)。

Input Format

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。

Output Format

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

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

6

Hint

Choose jobs $1,4,3,5$ respectively, and the total profit is $3+2-5+6 = 6$.

• 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