Problem D
Verkliðir

Fyrirtækjarekstur þinn gengur vel. Eins og stendur getur þú valið milli $N$ verkliða, númeruð frá $1$ til $N$, sem bíða eftir því að vera kláruð. Þessir verkliðir endurnýjast ekki.

Með því að klára verklið $i$ hagnast þú um $x_ i$ evrur. Það getur verið að hagnaðurinn sé neikvæður ($x_ i < 0$) og táknar þá tap.

Sumir verkliðir eru með forkröfur. Það er að segja, til þess að byrja á verklið $i$ þarf að klára verklið $p_ i$ fyrst. Því getur verkliður með miklum gróða verið minna aðlaðandi ef klára þarf verkliði með miklu tapi til að byrja á því fyrst. Ef $p_ i = 0$ táknar það að verkliður $i$ sé ekki með neinar forkröfur og vinna megi þann verklið án þess að klára neitt annað fyrst.

Þú átt $s$ evrur eins og stendur og getur ráðið hvaða verkliði þú tekur að þér og í hvaða röð, svo lengi sem þú virðir forkröfur verkliða. Þú mátt aldrei eyða meiri pening en þú hefur, það er að segja, peningurinn sem þú hefur á sérhverjum tímapunkti má ekki vera neikvæður.

Verkefni

Ákvarðið hámarksgróða sem hægt er að ná með því að klára eitthvert (mögulega tómt) hlutmengi $N$ verkliðanna í einhverri röð.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $N$ og $s$, fjöldi verkliða og fjölda evra sem þú hefur upphaflega.

Næst fylgja $N$ línur. $i$-ta línan inniheldur tvær heiltölur $x_ i$ og $p_ i$, hagnaður $i$-ta verkliðsins og númer verkliðsins sem er forkrafa $i$-ta verkliðsins. Ef $p_ i = 0$ hefur $i$-ta verkliðurinn ekki neina forkröfu.

Úttak

Forrit þitt á að prenta eina heiltölu, hæsta mögulega gróða sem þú getur náð.

Sýnidæmi

Til að hámarka gróða skal velja verklið 1, 3, 5 og 6 í eftirfarandi röð:

• Verkliður 1: Evrur $1 \rightarrow 4$,

• Verkliður 4 (forkrafan 1 kláruð): Evrur $4 \rightarrow 6$,

• Verkliður 3: Evrur $6 \rightarrow 1$,

• Verkliður 5 (forkrafan 3 kláruð): Evrur $1 \rightarrow 7$.

Samtals er gróðinn $7 - 1 = 6$ (núverandi fjöldi evra mínus upphafsfjöldi evra).

Takmarkanir

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

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

• $-10^9 \leq x_ i \leq 10^9$ (fyrir öll $1 \leq i \leq N$)

• $0 \leq p_ i < i$ (fyrir öll $1 \leq i \leq N$)

Hlutverkefni

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

6