Problem D
Jobs

You have a successful business where you make money by completing jobs for your clients. Currently, you can choose from $N$ one-time jobs, numbered from $1$ to $N$.

Completing job $i$ will make you a profit of $x_ i$ euros. The profit may also be negative ($x_ i < 0$).

Some jobs depend on another job. That is, there may be a job numbered $p_ i$ that must be completed before the $i$-th job can be started. Hence, a job with a large profit may be less attractive than it seems if it depends on a job with a negative profit. If $p_ i = 0$, the $i$-th job has no dependency.

You currently have $s$ euros and can decide which jobs to do and in which order to do them, as long as the dependencies are respected. Moreover, the amount of money you own may not become negative at any point.

Task

Calculate the maximum profit you can make by choosing to complete some (possibly none) of the $N$ jobs in a selected order.

Input

The first line contains two integers $N$ and $s$ – the number of jobs and the amount of money you initially own respectively.

Then, $N$ lines follow. The $i$-th of them contains two integers $x_ i$ and $p_ i$ – the profit and the number of the prerequisite job for the $i$-th job, respectively. If $p_ i = 0$, the $i$-th job does not have a job dependency.

Output

Your program should output a single integer – the maximum profit that you can make.

Examples

To maximize profit, you should pick jobs 1, 4, 3 and 5 in the following order:

• Job 1: money $1 \rightarrow 4$,

• Job 4 (prerequisite 1 complete): money $4 \rightarrow 6$,

• Job 3: money $6 \rightarrow 1$,

• Job 5 (prerequisite 3 complete): money $1 \rightarrow 7$.

Overall, the total profit is $7 - 1 = 6$ (current money minus starting money).

Constraints

• $1 \leq N \leq 3 \cdot 10^5$

• $0 \leq s \leq 10^{18}$

• $-10^9 \leq x_ i \leq 10^9$ (for all $1 \leq i \leq N$)

• $0 \leq p_ i < i$ (for all $1 \leq i \leq N$)

Subtasks

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

6