#include <bits/stdc++.h>
#define sz(s) (int)s.size()
using namespace std;
const int MAXN = 3e5+5;
typedef long long ll;
const ll inf = 1e18;
int n;
vector<int> nxt[MAXN];
ll val[MAXN];
ll mx_val[MAXN];
vector<int> rts;
ll s;
typedef array<ll, 2> ar2;
void shift(int v, vector<ar2> &profit) {
vector<ar2> nxt;
ll oval = 0;
for (ar2 a: profit) {
if (a[0] <= v) {
oval = max(oval, a[1]);
}
else {
if (oval != 1) {
nxt.push_back({0, max(0ll, v+oval)});
oval = -1;
}
if (a[1]+v > 0) nxt.push_back({a[0]-v, a[1]+v});
}
}
if (oval != -1) nxt.push_back({0, max(0ll, v+oval)});
profit = nxt;
}
ll nxt_pos(ll pos, int ind, vector<ar2> &vals, int ex) {
if (ind == sz(vals)-1) return inf;
return vals[ind+1][0]-ex;
}
void move_up(ll pos, int &l, int &r, vector<ar2> &a, vector<ar2> &b) {
bool f = 1;
while (f) {
f = 0;
if (pos >= nxt_pos(pos, r, b, a[l][1])) {
r++;
f = 1;
}
if (pos >= nxt_pos(pos, l, a, b[r][1])) {
l++;
f = 1;
}
}
}
vector<ar2> merge(vector<ar2> &a, vector<ar2> &b) {
vector<ar2> ans;
int l = 0, r = 0;
ll pos = 0;
while (1) {
move_up(pos, l, r, a, b);
ans.push_back({pos, a[l][1]+b[r][1]});
if (l+r == sz(a) + sz(b) - 2) break;
pos = min(nxt_pos(pos, l, a, b[r][1]),
nxt_pos(pos, r, b, a[l][1]));
}
return ans;
}
ll dfs(int cur) {
ll res = 0;
for (int v: nxt[cur]) {
res += dfs(v);
}
return max(0ll,res+val[cur]);
}
void solve1() {
ll ans = 0;
for (int i: rts) ans += dfs(i);
cout << ans << '\n';
}
typedef priority_queue<ar2, vector<ar2>, greater<ar2>> pq;
ll pval[MAXN];
void make_prof(pq &prof, int cur, ll sm = 0, ll mn = 0) {
sm += val[cur];
mn = min(mn, sm);
if (sm > 0) {
prof.push({-mn, cur});
pval[cur] = sm;
return;
}
if (!nxt[cur].empty()) make_prof(prof, nxt[cur][0], sm, mn);
}
void solve2() {
pq prof;
for (int rt: rts) {
make_prof(prof, rt);
}
ll o = s;
while (!prof.empty()) {
ar2 t = prof.top();
prof.pop();
if (s < t[0]) break;
s += pval[t[1]];
if (!nxt[t[1]].empty()) make_prof(prof, nxt[t[1]][0]);
}
cout << s-o << '\n';
}
vector<ar2> build(int cur) {
vector<ar2> ans({{0, 0}});
for (int v: nxt[cur]) {
vector<ar2> cur = build(v);
ans = merge(ans, cur);
}
shift(val[cur], ans);
return ans;
}
void solve3() {
vector<ar2> ans({{0, 0}});
for (int rt: rts) {
vector<ar2> cur = build(rt);
ans = merge(ans, cur);
}
int ind = upper_bound(ans.begin(), ans.end(), ar2({s, inf}))-ans.begin();
assert(ind);
cout << ans[ind-1][1] << '\n';
}
bool chk_nxt() {
for (int i = 0; i < n; i++) {
if (sz(nxt[i]) > 1) return 0;
}
return 1;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> s;
for (int i = 0; i < n; i++) {
int p; cin >> val[i] >> p;
if (p == 0) rts.push_back(i);
else nxt[p-1].push_back(i);
}
if (s == inf) solve1();
else if (chk_nxt()) solve2();
else if (n <= 2000) solve3();
else assert(false);
}
