#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef pair<int, int> pi;
typedef pair<ll, pi> pli;
typedef vector<ll> vl;
typedef vector<vl> v2l;
typedef vector<bool> vb;
typedef priority_queue<pli> pq;
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < n; i++)
//sub 1, 2, 3
vl p;
v2i adj;
vi par;
vl tp;
vb done;
vl req;
int nextjob;
int njd; // next job depth
ll m; // current money
bool sub3;
ll sub3solve() {
v2l chains, req, tp;
chains.resize(p.size());
req.resize(p.size());
tp.resize(p.size());
pq nextjobs;
// building chains
for (auto start : adj[0]) {
ll ctp = 0, creq = 0, pmr = 0, job = start;
//cout << "\nCreating chain:";
bool endchain = false;
while (!endchain) {
ctp += p[job];
pmr += p[job];
if (pmr < 0) {
creq -= pmr;
pmr = 0;
}
if (ctp > 0) {
chains[start].pb(job);
req[start].pb(0 - creq);
tp[start].pb(ctp);
ctp = 0; creq = 0; pmr = 0;
if (chains[start].size() == 1) {
nextjobs.push({ 0 - creq, {start, 0} });
}
//cout << " " << job;
}
if (adj[job].size() == 0) {
endchain = true;
}
else {
job = adj[job][0];
}
}
}
//cout << "\nChains built\n";
//using the chains
while (nextjobs.size() > 0 && 0 - nextjobs.top().first <= m) {
//int req = nextjobs.top().first;
int start = nextjobs.top().second.first;
int index = nextjobs.top().second.second;
nextjobs.pop();
m += tp[start][index];
if (index + 1 < tp[start].size()) {
nextjobs.push({ req[start][index + 1], {start, index + 1} });
}
}
return m;
}
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);
sub3 = true;
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 (p_i != i && p_i != 0) sub3 = false;
}
if (s == 1e18) {
cout << dfs(0) - s;
return 0;
}
//if (sub3) {
// //cout << "Subtask 3 detected\n";
// m = s;
// cout << sub3solve() - s;
// 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;
m += p[j];
j = par[j];
}
//cout << "Current money: " << m << "\n-------------------------------------------------------------\n";
nextjob = -1;
njd = 0;
}
cout << m - s;
return 0;
}
