/*
* Author: Nonoze
* Created: Sunday 05/05/2024
*/
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
#define int long long
#ifndef _IN_LOCAL
#define dbg(...) ;
#endif
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) {cout << x << endl; return;}
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;
void solve();
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;
// cin >> tt;
while(tt--) solve();
return 0;
}
struct Segtree {
int n;
vector<int> tree, values;
vector<pair<int, int>> lazy;
Segtree(int _n) {
n = _n;
tree.resize(4*n, -inf);
values.resize(4*n, -inf);
lazy.resize(4*n, {-1, inf});
}
void build(vector<pair<int, int>> &a) {
build(a, 1, 0, n-1);
}
void build(vector<pair<int, int>> &a, int v, int l, int r) {
if (l == r) {
tree[v] = a[l].fi;
values[v] = a[l].se;
return;
}
int m = (l+r)/2;
build(a, 2*v, l, m);
build(a, 2*v+1, m+1, r);
int ans=-inf;
if (l!=m || values[2*v]>=0) cmax(ans, tree[2*v]);
if (m+1!=r || values[2*v+1]>=0) cmax(ans, tree[2*v+1]);
tree[v] = ans;
}
void push(int v, int l, int r) {
if (lazy[v].fi == -1) return;
tree[v] += lazy[v].fi; cmin(tree[v], lazy[v].se);
if (l != r) {
if (lazy[2*v].fi == -1) lazy[2*v].fi = 0;
if (lazy[2*v+1].fi == -1) lazy[2*v+1].fi = 0;
lazy[2*v].fi += lazy[v].fi;
lazy[2*v+1].fi += lazy[v].fi;
cmin(lazy[2*v].se, lazy[v].se);
cmin(lazy[2*v+1].se, lazy[v].se);
}
lazy[v] = {-1, inf};
}
void update(int v, int l, int r, int ql, int qr, pair<int, int> val, int val2) {
push(v, l, r);
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
if (val.fi==-inf) {
tree[v] = val.se;
return;
}
if (val2!=-inf) values[v] = val2;
lazy[v] = val;
push(v, l, r);
return;
}
int m = (l+r)/2;
update(2*v, l, m, ql, qr, val, val2);
update(2*v+1, m+1, r, ql, qr, val, val2);
int ans=-inf;
if (l!=m || values[2*v]>=0) cmax(ans, tree[2*v]);
if (m+1!=r || values[2*v+1]>=0) cmax(ans, tree[2*v+1]);
tree[v] = ans;
}
void update(int l, int r, int val, int val2, int val3) {
update(1, 0, n-1, l, r, {val, val2}, val3);
}
int query(int v, int l, int r, int required) {
push(v, l, r);
if (required + tree[v] < 0) return -1;
if (l == r) return l;
int m = (l+r)/2;
push(2*v, l, m); push(2*v+1, m+1, r);
cout << l << " " << r << " " << tree[v] << " " << values[v] << endl;
if (l==m && values[2*v]<0) return query(2*v+1, m+1, r, required);
if (m+1==r && values[2*v+1]<0) return query(2*v, l, m, required);
if (tree[2*v]>tree[2*v+1]) return query(2*v, l, m, required);
return query(2*v+1, m+1, r, required);
}
int query(int required) {
return query(1, 0, n-1, required);
}
int que(int v, int l, int r, int empl) {
push(v, l, r);
if (l == r) return tree[v];
int m = (l+r)/2;
if (empl <= m) return que(2*v, l, m, empl);
return que(2*v+1, m+1, r, empl);
}
int que(int empl) {
return que(1, 0, n-1, empl);
}
};
int n, k, leftt;
vector<int> a, p, minii, pref, in, out;
vector<set<int>> adj;
int comp=0;
void dfsmini(int i, int sum, int mini) {
sum+=a[i]; cmin(mini, sum); minii[i]=mini; pref[i]=sum;
in[i]=comp++;
for (auto u: adj[i]) dfsmini(u, sum, mini);
out[i]=comp++;
}
pair<pair<int, int>, int> dfs(int i, int sum, int mini) {
sum+=a[i]; cmin(mini, sum);
if (sum >= 0 && i) return {{mini, sum}, i};
vector<pair<pair<int, int>, int>> res;
for (auto u: adj[i]) {
auto temp=dfs(u, sum, mini);
if (temp.se!=-1) res.pb(temp);
}
if (res.empty()) return {{-1, -1}, -1};
sort(rall(res));
return res[0];
}
void solve() {
cin >> n >> k; n++;
a.resize(n), p.resize(n), adj.resize(n), minii.resize(n, 0), in.resize(n), out.resize(n), pref.resize(n);
for (int i=1; i<n; i++) {
cin >> a[i] >> p[i];
adj[p[i]].insert(i);
}
dfsmini(0, 0, 0);
for (int tt=0; tt<n; tt++) {
for (int i=1; i<n; i++) {
if (a[i]>=0 && minii[p[i]]+k>=0) {
a[p[i]]+=a[i];
adj[p[i]].erase(i);
for (auto u: adj[i]) {
adj[p[i]].insert(u);
p[u]=p[i];
}
adj[i].clear();
a[i]=-inf;
dfsmini(0, 0, 0);
}
}
}
// vector<pair<int, int>> tobuild(comp, {-inf, -inf});
// map<int, int> mp;
// for (int i=1; i<n; i++) {
// tobuild[in[i]]={minii[i], pref[i]};
// tobuild[out[i]]={minii[i], pref[i]};
// mp[in[i]]=i;
// mp[out[i]]=i;
// }
// Segtree seg(comp); seg.build(tobuild);
// for (int t=0; t<n; t++) {
// int i=seg.query(k);
// cout << i << " " << mp[i] << " " << pref[mp[i]] << endl;
// if (i==-1) break;
// i=mp[i];
// if (a[i]>=0) {
// a[p[i]]+=a[i];
// adj[p[i]].erase(i);
// for (auto u: adj[i]) {
// adj[p[i]].insert(u);
// p[u]=p[i];
// }
// adj[i].clear();
// int mini=0;
// if (p[i]!=0) mini=seg.que(in[p[i]]);
// seg.update(in[p[i]], in[i]-1, a[i], mini, -inf);
// seg.update(out[i]+1, out[p[i]], a[i], mini, -inf);
// seg.update(in[p[i]], in[p[i]], -inf, seg.que(in[p[i]]), a[p[i]]);
// seg.update(out[p[i]], out[p[i]], -inf, seg.que(out[p[i]]), a[p[i]]);
// a[i]=-inf;
// }
// seg.update(in[i], in[i], -inf, -inf, -inf);
// seg.update(out[i], out[i], -inf, -inf, -inf);
// }
leftt=k+a[0]; a[0]=0;
int sum=0, mini=0;
auto base=dfs(0, 0, 0);
while (base.se != -1 && leftt + base.fi.fi >= 0) {
int i = base.se;
sum=0; int par=i;
vector<int> begining;
while (par != 0) {
sum += a[par];
adj[p[par]].erase(par);
for (auto u: adj[par]) p[u]=0, adj[0].insert(u);
adj[par].clear();
par = p[par];
}
if (sum<0) break;
leftt += sum;
base=dfs(0, 0, 0);
}
cout << leftt-k << endl;
return;
}
