// Author: caption_mingle
#include "bits/stdc++.h"
using namespace std;
#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e18;
const int N = 3e5 + 7;
int n, s, a[N], p[N];
struct SEGTREE {
int n;
vector<pair<int, int>> st;
vector<int> lazy;
SEGTREE() {}
SEGTREE(int n) {
st.resize(n * 4 + 4, {0, 0});
lazy.resize(n * 4 + 4, 0);
}
void build(int i, int l, int r) {
if(l == r) {
st[i] = {-inf, l};
return;
}
int m = (l + r) >> 1;
build(i * 2, l, m);
build(i * 2 + 1, m + 1, r);
st[i] = max(st[i * 2], st[i * 2 + 1]);
}
void down(int i) {
if(lazy[i]) {
int x = lazy[i];
lazy[i] = 0;
lazy[i * 2] += x;
lazy[i * 2 + 1] += x;
st[i * 2].fi += x;
st[i * 2 + 1].fi += x;
}
}
void update(int i, int l, int r, int u, int v, int x) {
if(l > v or r < u) return;
if(u <= l and r <= v) {
st[i].fi += x;
lazy[i] += x;
return;
}
int m = (l + r) >> 1;
update(i * 2, l, m, u, v, x);
update(i * 2 + 1, m + 1, r, u, v, x);
st[i] = max(st[i * 2], st[i * 2 + 1]);
}
pair<int, int> get(int i, int l, int r, int u, int v) {
if(l > v or r < u) return {-inf, 0};
if(u <= l and r <= v) return st[i];
int m = (l + r) >> 1;
return max(get(i * 2, l, m, u, v), get(i * 2 + 1, m + 1, r, u, v));
}
};
namespace sub1 {
bool check() {
return s == 1e18;
}
int id[N], root[N], f[N];
int cur = 0;
vector<int> g[N];
void dfs(int u) {
id[u] = cur;
for(int v : g[u]) {
dfs(v);
}
}
void dfs2(int u) {
f[u] = 0;
int ext = 0;
for(int v : g[u]) {
dfs2(v);
ext += f[v];
}
f[u] = max(f[u], ext + a[u]);
}
void solve() {
for(int i = 1; i <= n; i++) {
if(p[i] != 0) {
g[p[i]].pb(i);
}
}
for(int i = 1; i <= n; i++) {
if(p[i] == 0) {
cur++;
root[cur] = i;
dfs(i);
}
}
int ans = 0;
for(int i = 1; i <= cur; i++) {
dfs2(root[i]);
ans += f[root[i]];
}
cout << ans << ln;
}
}
namespace sub2 {
bool check() {
for(int i = 1; i <= n; i++) {
if(p[i] == 0 or p[i] == i - 1) continue;
return 0;
}
return 1;
}
int mn[N], val[N], lst[N], fir[N], grp[N];
int gp = 0;
void solve() {
mn[0] = inf;
for(int i = 1; i <= n; i++) {
val[i] = val[p[i]] + a[i];
mn[i] = min(val[i], mn[p[i]]);
if(p[i] == 0) {
grp[i] = ++gp;
fir[gp] = i;
} else grp[i] = grp[i - 1];
}
SEGTREE st = SEGTREE(n);
st.build(1, 1, n);
int ans = 0;
for(int i = n; i > 0; i--) {
if(p[i + 1] == 0) {
lst[grp[i]] = i;
}
}
vector<pair<int, int>> vec;
for(int i = 1; i <= n; i++) {
vec.pb({mn[i], i});
}
sort(all(vec), greater<pair<int, int>>());
int i = 0;
while(1) {
if(i < sz(vec) and vec[i].fi + s >= 0) {
auto [min_val, u] = vec[i];
if(min_val + s >= 0) {
// cerr << "UPDATE " << u << ' ' << val[u] << ln;
st.update(1, 1, n, u, u, val[u] + inf);
i++;
}
} else {
auto [x, id] = st.st[1];
// cerr << "GET " << x << ' ' << id << ln;
if(x <= 0) break;
ans += x;
s += x;
int cur_grp = grp[id];
int old_fir = fir[cur_grp];
for(int j = old_fir; j <= id; j++) {
st.update(1, 1, n, j, j, -inf);
}
fir[cur_grp] = id + 1;
if(fir[cur_grp] <= lst[cur_grp]) {
st.update(1, 1, n, id + 1, lst[cur_grp], -val[id]);
}
}
}
cout << ans << ln;
}
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#define task ""
if(fopen(task ".INP", "r")) {
freopen(task ".INP", "r", stdin);
freopen(task ".OUT", "w", stdout);
}
cin >> n >> s;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> p[i];
}
if(sub1::check()) sub1::solve();
else if(sub2::check()) sub2::solve();
cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}
