#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef pair<int, int> pi;
typedef vector<ll> vl;
typedef vector<vl> v2l;
typedef vector<bool> vb;
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < n; i++)
//sub 1
vl p;
v2i adj;
vi par;
vl tp;
vb done;
vl req;
int nextjob;
int njd; // next job depth
ll m; // current money
ll dfs(int x) {
// use dfs to find the maximum possible profit given that you do job x
ll s = p[x];
for (auto a : adj[x]) {
s += max(0ll, dfs(a));
}
return s;
}
bool dfsu(int x, ll ctp=0, ll creq = 0, ll pmr=0, int depth=0) {
// use dfs to update the current node, and returns if a new next job was found
// tp: the total profit gained if this job is done
// req: the total money requirement of going to this job
// pmr: the total positive money reserve
tp[x] = ctp;
req[x] = creq;
if (creq <= m && ctp > 0 && depth > njd) {
nextjob = x;
njd = depth;
return true;
}
//cout << "Jobs upto job " << x << " can now be done with profit " << ctp << " and require " << creq << "\n";
for (auto a : adj[x]) {
if (!done[a]) {
if (pmr + p[a] < 0) {
if (dfsu(a, ctp + p[a], creq - (pmr + p[a]), 0, depth + 1)) {
return true;
}
}
else if (dfsu(a, ctp + p[a], creq, pmr + p[a], depth + 1)) {
return true;
}
}
else {
if (dfsu(a)) {
return true;
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
ll s;
cin >> n >> s;
//if (s < 10e17) return 1;
p.pb(s);
par.pb(-1);
adj.resize(n + 1);
done.resize(n + 1, false); done[0] = true;
tp.resize(n + 1);
req.resize(n + 1);
par.resize(n + 1, 0);
ll x, p_i;
rep(i, n) {
cin >> x >> p_i;
adj[p_i].pb(i + 1);
par[i + 1] = p_i;
p.pb(x);
}
if (s >= (3 * 10e5 - 1) * 10e9) {
cout << dfs(0);
return 0;
}
m = s;
nextjob = -1;
njd = 0;
while (dfsu(0)) {
int j = nextjob;
//cout << "Jobs upto job " << j << " were done with profit " << tp[j] << "\n";
while (!done[j]) {
done[j] = true;
j = par[j];
}
m += tp[nextjob];
//cout << "Current money: " << m << "\n-------------------------------------------------------------\n";
nextjob = -1;
njd = 0;
}
cout << m - s;
return 0;
}
