#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p;
DSU(int n = 0) { init(n); }
void init(int n) {
p.resize(n + 1);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
ll s;
cin >> N >> s;
DSU dsu(N);
vector<int> parentOf(N + 1, -1); // parent component pointer; current parent = find(parentOf[x])
vector<ll> need(N + 1, 0), gain(N + 1, 0);
vector<int> ver(N + 1, 0);
// child heaps: for each live component p, candidates for profitable current children of p
using ChildEntry = tuple<ll, int, int>; // (need_snapshot, child_id, child_version)
vector<priority_queue<ChildEntry, vector<ChildEntry>, greater<ChildEntry>>> childHeap(N + 1);
// global profitable blocks eligible for HARD merge:
// current parent must exist and must not be fake root 0
priority_queue<ChildEntry, vector<ChildEntry>, greater<ChildEntry>> hardHeap;
// global possible EASY merges:
// delta = child.need - (parent.need + parent.gain)
using EasyEntry = tuple<ll, int, int, int, int>; // (delta, p, verP, c, verC)
priority_queue<EasyEntry, vector<EasyEntry>, greater<EasyEntry>> easyHeap;
auto getParent = [&](int x) -> int {
if (parentOf[x] == -1) return -1;
return dsu.find(parentOf[x]);
};
// fake root 0
parentOf[0] = -1;
need[0] = 0;
gain[0] = s;
for (int i = 1; i <= N; i++) {
ll x;
int p;
cin >> x >> p;
gain[i] = x;
need[i] = max<ll>(0, -x);
parentOf[i] = p; // parent in initial tree, with fake root 0
}
auto isHardEligible = [&](int x) -> bool {
int p = getParent(x);
return p != -1 && p != 0;
};
auto cleanChildren = [&](int p) {
p = dsu.find(p);
auto &pq = childHeap[p];
while (!pq.empty()) {
auto [snapNeed, c, snapVer] = pq.top();
int rc = dsu.find(c);
if (rc != c) {
pq.pop();
continue;
}
if (ver[c] != snapVer) {
pq.pop();
continue;
}
if (gain[c] < 0) {
pq.pop();
continue;
}
if (getParent(c) != p) {
pq.pop();
continue;
}
break;
}
};
auto refreshParent = [&](int p) {
p = dsu.find(p);
cleanChildren(p);
if (!childHeap[p].empty()) {
auto [snapNeed, c, snapVer] = childHeap[p].top();
ll delta = need[c] - (need[p] + gain[p]);
easyHeap.push({delta, p, ver[p], c, ver[c]});
}
};
auto pushProfitableBlock = [&](int x) {
x = dsu.find(x);
if (gain[x] < 0) return;
int p = getParent(x);
if (p != -1) {
childHeap[p].push({need[x], x, ver[x]});
}
if (isHardEligible(x)) {
hardHeap.push({need[x], x, ver[x]});
}
};
for (int i = 1; i <= N; i++) {
if (gain[i] >= 0) pushProfitableBlock(i);
}
for (int i = 0; i <= N; i++) refreshParent(i);
auto meldHeaps = [&](int a, int b) {
if (childHeap[a].size() < childHeap[b].size()) swap(a, b);
while (!childHeap[b].empty()) {
childHeap[a].push(childHeap[b].top());
childHeap[b].pop();
}
return pair<int, int>{a, b}; // merged into a, b becomes dead
};
auto validEasyTop = [&]() -> optional<pair<int,int>> {
while (!easyHeap.empty()) {
auto [delta, p, vp, c, vc] = easyHeap.top();
p = dsu.find(p);
if (p != get<1>(easyHeap.top())) {
easyHeap.pop();
continue;
}
if (ver[p] != vp) {
easyHeap.pop();
continue;
}
cleanChildren(p);
if (childHeap[p].empty()) {
easyHeap.pop();
continue;
}
auto [snapNeed, realC, realVC] = childHeap[p].top();
ll realDelta = need[realC] - (need[p] + gain[p]);
if (realC != c || realVC != vc || realDelta != delta) {
easyHeap.pop();
continue;
}
return pair<int,int>{p, c};
}
return nullopt;
};
auto validHardTop = [&]() -> optional<int> {
while (!hardHeap.empty()) {
auto [snapNeed, x, vx] = hardHeap.top();
x = dsu.find(x);
if (x != get<1>(hardHeap.top())) {
hardHeap.pop();
continue;
}
if (ver[x] != vx) {
hardHeap.pop();
continue;
}
if (gain[x] < 0) {
hardHeap.pop();
continue;
}
if (!isHardEligible(x)) {
hardHeap.pop();
continue;
}
return x;
}
return nullopt;
};
auto mergeBlocks = [&](int p, int c, bool easy) {
p = dsu.find(p);
c = dsu.find(c);
// Current parent of c must be p
int gp = getParent(p); // parent of the merged block after contraction
ll newGain = gain[p] + gain[c];
ll newNeed;
if (easy) {
// easy case implies max(need[p], need[c] - gain[p]) = need[p]
newNeed = need[p];
} else {
// hard case implies the active branch is need[c] - gain[p]
newNeed = need[c] - gain[p];
}
// small-to-large on child heaps; representative can be either p or c
int rep, dead;
tie(rep, dead) = meldHeaps(p, c);
dsu.p[dead] = rep;
if (rep == c) {
// merged component replaces parent p in the tree
parentOf[rep] = gp;
}
// if rep == p, parentOf[p] already equals gp
gain[rep] = newGain;
need[rep] = newNeed;
ver[rep]++;
ver[dead]++; // invalidate stale entries mentioning dead
if (gain[rep] >= 0) {
int par = getParent(rep);
if (par != -1) {
childHeap[par].push({need[rep], rep, ver[rep]});
refreshParent(par);
}
if (isHardEligible(rep)) {
hardHeap.push({need[rep], rep, ver[rep]});
}
}
refreshParent(rep);
if (gp != -1) refreshParent(gp);
};
while (true) {
// Exhaust all easy merges first
while (true) {
auto cand = validEasyTop();
if (!cand.has_value()) break;
int p = cand->first;
int c = cand->second;
ll delta = need[c] - (need[p] + gain[p]);
if (delta > 0) break;
mergeBlocks(p, c, true);
}
auto hard = validHardTop();
if (!hard.has_value()) break;
int x = *hard;
int p = getParent(x);
mergeBlocks(p, x, false);
}
cout << gain[dsu.find(0)] << '\n';
return 0;
}
