#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
const ll N = 1e6 + 2;
vector < ll > adj[N];
ll depth[N], cost[N], sz[N], a[N], pos[N];
ll timer = 0, n;
ll anc[N], par[N];
vector < pair < ll, ll > > dep;
struct ST {
ll mn, sum, has = 0;
};
ST F;
ST T[4 * N];
void Build(ll p, ll lo, ll hi) {
if ( lo == hi){
T[p].mn = a[lo];
T[p].sum = a[lo];
T[p].has = 0;
return ;
}
ll mid = (lo + hi)/2;
Build(2 * p, lo, mid);
Build(2 * p + 1, mid + 1, hi);
T[p].sum = T[2 * p].sum + T[2 * p + 1].sum;
T[p].mn = min(T[2 * p + 1].mn ,T[2 * p + 1].mn);
T[p].has = 0;
}
void PushDown(ll p, ll lo, ll hi) {
if ( T[p].has == 0) return ;
T[p].sum = T[p].mn = 0;
if ( lo == hi) return ;
T[2 * p].has = T[2 * p + 1].has = 1;
return ;
}
void Find(ll p, ll lo, ll hi, ll l, ll r) {
PushDown(p, lo, hi);
if ( l > hi || lo > r) return ;
if ( l <= lo && hi <= r) {
F.mn = min(F.mn, T[p].mn);
F.sum = F.sum + T[p].sum;
return ;
}
ll mid = (lo + hi)/2;
Find(2 * p, lo, mid, l, r);
Find(2 * p + 1, mid + 1, hi, l, r);
return ;
}
void Update(ll p, ll lo, ll hi, ll l, ll r) {
PushDown(p, lo, hi);
if ( l > hi || lo > r) return ;
if ( l <= lo && hi <= r) {
T[p].has = 1;
return ;
}
ll mid = (lo + hi)/2;
Update(2 * p, lo, mid, l, r);
Update(2 * p + 1, mid + 1, hi, l, r);
return ;
}
void query(ll x, ll y) {
F.mn =1e18;
F.sum = 0;
while ( anc[x] != anc[y]) {
if ( depth[anc[x]] < depth[anc[y]] ) swap(x, y);
Find(1, 1, n + 1, pos[anc[x]], pos[x]);
x =par[anc[x]];
}
if ( pos[x] > pos[y]) swap(x, y);
Find(1, 1, n + 1, pos[x], pos[y]);
}
void update_query(ll x, ll y) {
F.mn =1e18;
F.sum = 0;
for ( ; anc[x] != anc[y]; x = par[anc[x]]) {
if ( depth[anc[x]] < depth[anc[y]] ) swap(x, y);
Update(1, 1, n + 1, pos[anc[x]], pos[x]);
}
if ( pos[x] > pos[y]) swap(x, y);
Update(1, 1, n + 1, pos[x], pos[y]);
}
ll Go(ll node, ll par) {
sz[node] = 1;
for ( ll nxt : adj[node]) {
if ( nxt == par) continue;
depth[nxt] = depth[node] + 1;
sz[node] += Go(nxt, node);
}
return sz[node];
}
void HLD(ll node, ll par, ll king) {
timer ++;
a[timer] = cost[node];
pos[node] = timer;
anc[node] = king;
ll heavy_node , heavy_sz;
heavy_node = heavy_sz = -1;
for ( ll nxt :adj[node]) {
if ( nxt == par) continue;
if ( heavy_sz < sz[nxt]) {
heavy_sz = sz[nxt];
heavy_node = nxt;
}
}
if ( heavy_node == -1) return;
HLD(heavy_node, node, king);
for ( ll nxt : adj[node]) {
if ( nxt == par || nxt == heavy_node) continue;
HLD(nxt, node, nxt);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll m, r, s, y, i, ind, x, t;
cin >> n >> m;
for (i = 1; i <= n; i ++) {
cin >> cost[i] >> par[i];
adj[par[i]].push_back(i);
}
Go(0, 0);
HLD(0, 0, 0);
Build(1, 1, n + 1);
vector < pair < ll, ll > > v;
for (i = 0; i <= n; i++) {
v.push_back(make_pair(depth[i], i));
}
sort(v.begin(), v.end());
priority_queue < pair < ll, pll > > pq;
F.mn = 1e18;
F.sum = 0;
// for (i = 1; i <= n; i ++) {
// cout << anc[i] << " ";
// }
// cout << endl;
ll mn, sum, profit;
profit = 0;
for (ind = 0; ind < v.size(); ind ++) {
x = v[ind].second;
query(x, 0);
if ( F.sum <= 0) continue;
pq.push(make_pair(F.mn, make_pair(F.sum, x)));
while ( !pq.empty()) {
mn = pq.top().first;
sum= pq.top().second.first;
ind = pq.top().second.second;
if ( m + mn >= 0) {
m += sum;
profit +=sum;
update_query(ind, 0);
pq.pop();
}
else break;
}
}
cout << profit << endl;
}
