#include <bits/stdc++.h>
using namespace std;
#define int long long int
struct Fenw { // rupq
int n;
vector<int> BIT;
Fenw(int N) {
n = 2*N;
BIT.assign(n, 0);
}
void add(int idx, int delta) {
while (idx < n) {
BIT[idx] += delta;
idx = idx | (idx + 1);
}
}
void add(int l, int r, int delta) {
add(l, delta);
add(r, -delta);
}
int query(int r) {
int res = 0;
while (r >= 0) {
res += BIT[r];
r = (r & (r+1)) - 1;
}
return res;
}
};
vector<int> profit, dep, value, weight, tin, tout, used;
vector<set<int>> adj;
int timer = 0;
/* current need(u) = original weight(u) + ( currentGain(u) − originalGain(u) ) */
inline long long current_need(int u, Fenw& fenw) {
return weight[u] + fenw.query(tin[u]) - value[u];
}
/* multiset of (need, id) with **positive current gain** ----------------- */
multiset< pair<long long,int> > Q;
void push_if_profitable(int v, Fenw& fenw) {
if (used[v]) return;
long long gain = fenw.query(tin[v]);
if (gain > 0) Q.insert({ current_need(v, fenw), v });
};
/* unravel --------------------------------------------------------------- */
void unravel(int u, Fenw& fenw, long long& cash) { // Q is global
if (used[u]) return;
used[u] = 1;
/* children become independent → maybe profitable now */
for (int v : adj[u]) {
dep[v] = 0;
push_if_profitable(v, fenw);
}
adj[u].clear();
fenw.add(tin[u], tout[u], -profit[u]); // shift descendants
cash += profit[u];
if (dep[u]) unravel(dep[u], fenw, cash); // climb to parent
dep[u] = 0;
}
void dfs(int u, int curv, int min_weight) {
tin[u] = timer++;
curv += profit[u];
min_weight = min({0LL, min_weight, curv});
weight[u] = min_weight;
value[u] = curv;
for (auto &v : adj[u]) {
dfs(v, curv, min_weight);
}
tout[u] = timer;
}
signed main() {
int n, s; cin >> n >> s;
adj.assign(n+1, set<int>());
profit.resize(n+1); dep.resize(n + 1);
value.assign(n+1, 0); weight.assign(n+1, 0);
tin.assign(n+1, -1); tout.assign(n + 1, -1);
used.assign(n+1, 0);
for (int i = 1; i <= n; i++) {
cin >> profit[i] >> dep[i];
if(dep[i]) adj[dep[i]].insert(i);
}
/*
Idea: each j*b (j slur) forms a rooted tree with its dependencies
we can assign each node on tree a value (profit we can achieve with it) and a weight (money we need to achieve it)
we sort every node with positive value by weight and keep on adding, making sure to remove dp of all nodes earlier in the tree
if ever the min weight of a positive node is > current balance, stop
use a priority queue by profit for the exploration
*/
for (int i = 1; i <= n; i++) {
if (tin[i] != -1) continue;
dfs(i, 0, 0);
}
auto fenw = Fenw(2*n);
for (int i = 1; i <= n; i++) {
fenw.add(tin[i], tout[i], profit[i]);
}
int curs = s;
for (int i = 1; i <= n; ++i)
if (value[i] > 0) Q.insert({ weight[i], i });
while (!Q.empty()) {
auto [need_key, u] = *Q.begin();
Q.erase(Q.begin());
if (used[u]) continue; // outdated entry
long long gain_now = fenw.query(tin[u]);
long long need_now = current_need(u, fenw);
if (gain_now <= 0) continue; // no longer profitable
if (need_now > curs) break; // nothing else is affordable
unravel(u, fenw, curs); // execute the chain
}
cout << curs - s;
return 0;
}
