//chockolateman
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000000;
int N,a[300005],par[300005],p[300005],s[300005],lead[300005],tin[300005],tout[300005],timer,rev_tin[300005];
long long S,d[300005],prof[300005],dp[300005],ans;
bool used[300005],active[300005];
vector<int> adj[300005],active_edge[300005];
stack<int> to_buy;
void dfs1(int i)
{
stack<int> ord;
ord.push(i);
while(!ord.empty())
{
int v = ord.top();
ord.pop();
tin[v] = ++timer;
rev_tin[timer] = v;
prof[v] = prof[par[v]] + a[v];
d[v] = min(d[par[v]],prof[v]);
if(par[v]==0)
d[v] = prof[v];
for(auto u : adj[v])
{
if(u != par[v])
ord.push(u);
}
}
}
struct Node
{
long long maxim,pos,lazy = 0;
}st[1200005];
Node combine(Node left,Node right)
{
Node ret;
if(left.maxim >= right.maxim)
{
ret.maxim = left.maxim;
ret.pos = left.pos;
}
else
{
ret.maxim = right.maxim;
ret.pos = right.pos;
}
return ret;
}
void build(int v = 1,int start = 1,int end = N)
{
if(start==end)
{
st[v].maxim = d[rev_tin[start]];
st[v].pos = rev_tin[start];
st[v].lazy = 0;
return;
}
int mid = (start + end)/2;
build(2*v,start,mid);
build(2*v+1,mid+1,end);
st[v] = combine(st[2*v],st[2*v+1]);
}
void propagate(int v,int start,int end);
void update(int l,int r,long long val,int v = 1,int start = 1,int end = N)
{
if(start==l && end==r)
{
st[v].maxim += val;
st[v].lazy += val;
return;
}
propagate(v,start,end);
int mid = (start + end)/2;
if(r <= mid)
update(l,r,val,2*v,start,mid);
else if(l > mid)
update(l,r,val,2*v+1,mid+1,end);
else
{
update(l,mid,val,2*v,start,mid);
update(mid+1,r,val,2*v+1,mid+1,end);
}
st[v] = combine(st[2*v],st[2*v+1]);
}
void propagate(int v,int start,int end)
{
if(st[v].lazy)
{
int mid = (start + end)/2;
update(start,mid,st[v].lazy,2*v,start,mid);
update(mid+1,end,st[v].lazy,2*v+1,mid+1,end);
st[v].lazy = 0;
}
}
void activate(int pos,int v = 1,int start = 1,int end = N)
{
if(start==end)
{
st[v].maxim = - INF;
st[v].pos = 0;
return;
}
propagate(v,start,end);
int mid = (start + end)/2;
if(pos <= mid)
activate(pos,2*v,start,mid);
else
activate(pos,2*v+1,mid+1,end);
st[v] = combine(st[2*v],st[2*v+1]);
}
int find_Sett(int i)
{
if(p[i]==i)
return i;
p[i] = find_Sett(p[i]);
return p[i];
}
bool is_Same_Sett(int i,int j)
{
return find_Sett(i) == find_Sett(j);
}
long long dp_Sett(int i)
{
return dp[lead[find_Sett(i)]];
}
void union_Sett(int i,int j)
{
if(is_Same_Sett(i,j))
return;
int x = find_Sett(i);
int y = find_Sett(j);
if(s[x] < s[y])
swap(x,y);
p[y] = x;
s[x] += s[y];
if(lead[x] < lead[y])
dp[lead[x]] += dp[lead[y]];
else
{
dp[lead[y]] += dp[lead[x]];
lead[x] = lead[y];
}
}
void open(int v)
{
activate(tin[v]);
active[v] = true;
dp[v] = a[v];
s[v] = 1;
p[v] = v;
lead[v] = v;
for(auto u : adj[v])
if(u != par[v] && active[u] && dp[u] > 0)
{
active_edge[v].push_back(u);
active_edge[u].push_back(v);
union_Sett(v,u);
}
while(dp_Sett(v) >= 0)
{
int x = find_Sett(v);
if(used[par[lead[x]]])
{
to_buy.push(lead[x]);
break;
}
if(active[par[lead[x]]])
{
active_edge[par[lead[x]]].push_back(lead[x]);
active_edge[lead[x]].push_back(par[lead[x]]);
union_Sett(x,par[lead[x]]);
}
else
break;
}
}
void dfs2(int i) //buy
{
stack<int> ord;
ord.push(i);
while(!ord.empty())
{
int v = ord.top();
ord.pop();
S += a[v];
ans += a[v];
update(tin[v],tout[v],-a[v]);
used[v] = true;
for(auto u : active_edge[v])
if(u != par[v])
ord.push(u);
}
}
int main()
{
scanf("%d%lld",&N,&S);
for(int i = 1 ; i <= N ; i++)
{
scanf("%d%d",&a[i],&par[i]);
adj[i].push_back(par[i]);
adj[par[i]].push_back(i);
}
timer = -1;
dfs1(0);
used[0] = true;
for(int v = N ; v >= 1 ; v--)
{
tout[v] = tin[v];
for(auto u : adj[v])
if(u != par[v])
tout[v] = max(tout[v],tout[u]);
}
build();
bool moved = true;
while(moved)
{
moved = false;
while(st[1].pos > 0 && st[1].maxim + S >= 0)
{
moved = true;
open(st[1].pos);
}
if(!to_buy.empty())
{
moved = true;
int v = to_buy.top();
to_buy.pop();
if(!used[v])
dfs2(v);
}
}
printf("%lld\n",ans);
return 0;
}
