#include <bits/stdc++.h>
using namespace std;
// thank you geothermal :goat:
void __deb(int t) {cerr << t;}
void __deb(long t) {cerr << t;}
void __deb(long long t) {cerr << t;}
void __deb(unsigned int t) {cerr << t;}
void __deb(unsigned long t) {cerr << t;}
void __deb(unsigned long long t) {cerr << t;}
void __deb(float t) {cerr << t;}
void __deb(double t) {cerr << t;}
void __deb(long double t) {cerr << t;}
void __deb(char t) {cerr << '\'' << t << '\'';}
void __deb(const char *t) {cerr << '\"' << t << '\"';}
void __deb(const string &t) {cerr << '\"' << t << '\"';}
void __deb(bool t) {cerr << (t ? "true" : "false");}
template<typename T, typename V>
void __deb(const pair<T, V> &x){ cerr << '{'; __deb(x.first); cerr << ", "; __deb(x.second); cerr << '}'; }
template<typename T>
void __deb(const T &x){
int f = 0; cerr << '{';
for(auto &i: x){ if(f++) cerr << ", "; __deb(i);}
cerr << "}";
}
void _rdeb(vector<string> &names, int ind){}
template<typename T, typename... V>
void _rdeb(vector<string> &names, int ind, T t, V... v){
if(ind != 0) cerr << "==============\n";
cerr << names[ind] << '\n'; __deb(t); cerr << '\n';
_rdeb(names, ind+1, v...);
}
template<typename... V>
void _deb(string vars, V... v){
vector<string> names(1); int in{};
for(char c : vars)
if(c == ',' && in == 0){
while(names.back().size() && isspace(names.back().back())) names.back().pop_back();
names.push_back("");
}else{
if(c == '(') in++; if(c == ')') in--;
if(!isspace(c) || names.back().size()) names.back().push_back(c);
}
while(names.back().size() && isspace(names.back().back())) names.back().pop_back();
_rdeb(names, 0, v...);
}
#ifdef DEBUG
#define deb(x...) { \
cerr << __func__ << ':' << __LINE__ << '\n'; \
_deb(#x, x); \
cerr << '\n'; \
}
#define debsep(x...) { \
cerr << __func__ << ':' << __LINE__ << '\n'; \
_deb(#x, x); \
cerr << "****************************\n"; \
}
#else
#define deb(x...)
#define debsep(x...)
#endif
#define ar array
#define ll long long
typedef int uci;
#define int long long
#define F first
#define S second
typedef complex<double> cd;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define irep(i, a, b) for(int i = a; i > (b); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
#define ve vector
typedef ve<int> vi;
typedef ve<vi> vvi;
seed_seq seq{
(uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
(uint64_t) __builtin_ia32_rdtsc(),
(uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
// mt19937_64 lrng(seq);
struct debugger{
template <typename T>
debugger& operator<<(T &a){
#ifdef DEBUG
cerr << a;
#endif
return *this;
}
template <typename T>
debugger& operator<<(T &&a){
#ifdef DEBUG
cerr << a;
#endif
return *this;
}
} deb;
const double PI = acos(-1.0);
const int MAXN = 3e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
typedef ve<pair<ar<int, 2>, int>> segt;
//! function insert
//THINK FIRST, CODE SECOND
//DON'T GET STUCK ON ONE STRATEGY
//CALM DOWNNN FOR ONCE IN YOUR LIFE
//REDUCE
//COUGH E??!?!?!! O.O
//uwu i see you ryan
void update(int v, int val, int l, int r, int lq, int rq, segt &seg){
if(l > r || lq > r || rq < l)
return;
else if(lq <= l && r <= rq){
seg[v].S += val;
seg[v].F[0] += val;
}else{
int mid = l + (r-l)/2;
if(seg[v].S != 0){
update(v*2, seg[v].S, l, mid, l, mid, seg);
update(v*2+1, seg[v].S, mid+1, r, mid+1, r, seg);
seg[v].S = 0;
seg[v].F = max(seg[v*2].F, seg[v*2+1].F);
}
update(v*2, val, l, mid, lq, rq, seg);
update(v*2+1, val, mid+1, r, lq, rq, seg);
seg[v].F = max(seg[v*2].F, seg[v*2+1].F);
}
}
void sset(int v, ar<int, 2> val, int l, int r, int p, segt &seg){
if(l > r || p > r || p < l)
return;
else if(l == r && l == p){
seg[v].F = val;
seg[v].S = 0;
}else{
if(l == r)
return;
int mid = l + (r-l)/2;
if(seg[v].S != 0){
update(v*2, seg[v].S, l, mid, l, mid, seg);
update(v*2+1, seg[v].S, mid+1, r, mid+1, r, seg);
seg[v].S = 0;
seg[v].F = max(seg[v*2].F, seg[v*2+1].F);
}
sset(v*2, val, l, mid, p, seg);
sset(v*2+1, val, mid+1, r, p, seg);
seg[v].F = max(seg[v*2].F, seg[v*2+1].F);
}
}
ar<int, 2> query(int v, int l, int r, int lq, int rq, segt &seg){
if(l > r || lq > r || rq < l)
return {-LINF, -1};
else if(lq <= l && r <= rq){
return seg[v].F;
}else{
int mid = l + (r-l)/2;
return max(query(v*2, l, mid, lq, rq, seg), query(v*2+1, mid+1, r, lq, rq, seg));
}
}
int n;
int tt{};
int sdown[MAXN];
int wws[MAXN];
int tin[MAXN];
int tout[MAXN];
int lab[MAXN];
int marked[MAXN];
void dfs(int v, vvi &adj){
lab[tt] = v;
tin[v] = tt++;
for(int i : adj[v])
dfs(i, adj);
tout[v] = tt-1;
}
void markdown(int v, int s, int lim, vvi &adj, segt &seg, segt &add){
assert(!marked[v]);
sdown[v] = s;
if(s+lim < 0){
sset(1, {sdown[v], tin[v]}, 0, n-1, tin[v], seg);
return;
}
sset(1, {sdown[v], tin[v]}, 0, n-1, tin[v], add);
sset(1, {-LINF, -1}, 0, n-1, tin[v], seg);
for(int i : adj[v]){
markdown(i, s + wws[i], lim, adj, seg, add);
}
}
void markup(int v, vi &par, segt &seg, segt &add){
if(v == -1)
return;
if(marked[v])
return;
marked[v] = true;
update(1, -wws[v], 0, n-1, tin[v], tout[v], seg);
update(1, -wws[v], 0, n-1, tin[v], tout[v], add);
markup(par[v], par, seg, add);
}
void solve() {
int s;
cin >> n >> s;
vvi adj(n);
vi ins(n);
vi par(n, -1);
rep(i, 0, n){
int x, p;
cin >> x >> p;
wws[i] = x;
if(p != 0){
ins[i]++;
par[i] = p-1;
adj[p-1].push_back(i);
}
}
rep(i, 0, n)
if(ins[i] == 0)
dfs(i, adj);
int lim = s;
segt poss(4*n, {{-LINF, -1}, 0});
segt adds(4*n, {{-LINF, -1}, 0});
rep(i, 0, n){
if(ins[i] == 0){
markdown(i, wws[i], lim, adj, poss, adds);
}
}
int best = lim;
while(true){
ar<int, 2> t = adds[1].F;
if(t[1] != -1){
int st = lab[t[1]];
sset(1, {-LINF, -1}, 0, n-1, t[1], adds);
if(!marked[st] && lim+t[0] >= 0){
lim += t[0];
best = max(best, lim);
markup(st, par, poss, adds);
while(true){
ar<int, 2> ret = poss[1].F;
if(ret[1] != -1 && ret[0] + lim >= 0){
markdown(lab[ret[1]], ret[0], lim, adj, poss, adds);
}else
break;
}
}
}else
break;
}
cout << best - s << '\n';
}
uci main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// cout << "Case #" << t << ": ";
solve();
}
/*
random number generator stuff
num = rng(); gives integer number
num = uniform_int_distribution<int>(a, b)(rng); -> bounds [a, b]
num = uniform_real_distribution<double>(a, b)(rng); -> bounds [a, b)
can also instantiate distributions and call on generator:
uniform_int_distribution<int> thing(a, b);
num = thing(rng);
*/
// struct custom_hash {
// static uint64_t splitmix64(uint64_t x) {
// // http://xorshift.di.unimi.it/splitmix64.c
// x += 0x9e3779b97f4a7c15;
// x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
// x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
// return x ^ (x >> 31);
// }
// size_t operator()(uint64_t x) const {
// static const uint64_t FIXED_RANDOM = lrng();
// return splitmix64(x + FIXED_RANDOM);
// }
// };
