Job Selection under Capital Constraints

You are given N one‐time jobs numbered from 1 to N. Completing job i changes your money by x_i euros (this value can be negative), and some jobs may depend on another job. In particular, for each job i you are given an integer p_i such that if p_i ≠ 0 then job p_i must be completed before job i can be started. If p_i = 0, then job i has no dependency.

You start with s euros. You are free to select a subset of the jobs and decide the order in which to complete them as long as the dependency constraints are respected. However, at no point is your money allowed to become negative (i.e. your capital must always be at least 0).

Your task is to compute the maximum profit you can gain (i.e. the maximum net increase over your starting amount) by choosing an appropriate set of jobs and an order that respects both the dependency and the capital requirements. Note that if a job is selected, then all of its prerequisites (direct or indirect) must also be selected.

Mathematical formulation:

Let the jobs be represented by sequences with associated profits \(x_1, x_2, \dots, x_N\) and dependency pointers \(p_1, p_2, \dots, p_N\) (with the convention that a dependency of 0 means no dependency). If you choose a set \(S\) of jobs and order them as \(i_1, i_2, \dots, i_k\) such that for every job \(i_j\) with \(p_{i_j} \neq 0\) the job \(p_{i_j}\) appears in an earlier position, and if your running total defined by \[ M_0 = s, \quad M_j = M_{j-1} + x_{i_j} \quad (1 \le j \le k) \] satisfies \(M_j \ge 0\) for every \(j\), then the profit is \(M_k - s\). The goal is to maximize this profit over all valid choices of \(S\) and valid orderings.

inputFormat

The first line contains two space‐separated integers N and s (N is the number of jobs, and s is the starting amount of money).

Then follow N lines. The i-th of these lines contains two space-separated integers x and p where x is the profit (which can be negative) obtained by completing job i, and p is the job it depends on. If p = 0, then job i has no dependency.

Note: Jobs are numbered from 1 to N.

outputFormat

Output a single integer — the maximum profit (i.e. the maximum net increase to your starting money) achievable by completing a valid sequence of jobs.

sample

3 10
5 0
-3 1
7 2

9