#include <bits/stdc++.h>
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
#define nl '\n'
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
int64_t fund;
std::cin >> N >> fund;
std::vector<std::vector<int>> adj(N);
std::vector<int> x(N), p(N);
std::vector<int> deg(N);
for (int i = 0; i < N; i++) {
std::cin >> x[i] >> p[i];
--p[i];
if (p[i] != -1) {
deg[i]++;
adj[p[i]].emplace_back(i);
}
}
std::vector<int> st(N), en(N), who(N);
std::vector<int64_t> require(N), path(N);
int ti = 0;
std::vector<int64_t> dp(N + 1);
std::vector<int> take(N);
std::multiset<std::tuple<int64_t, int64_t, int>> s; // req, i
auto find_good = [&](int u) -> void {
require[u] = -x[u];
path[u] = -x[u];
for (int i = st[u] + 1; i < en[u]; i++) {
int v = who[i];
path[v] = path[p[v]] - x[v];
require[v] = std::max(require[p[v]], path[v]);
}
auto do_dp = [&](int64_t mb) {
dp[en[u]] = 0;
for (int i = en[u] - 1; i > st[u]; i--) {
int v = who[i];
take[v] = 0;
dp[i] = dp[en[v]]; // not taking this
if (require[v] <= mb) { // we can take it
if (dp[i] < dp[i + 1] + x[v]) {
take[v] = 1;
dp[i] = dp[i + 1] + x[v];
}
}
}
dp[st[u]] = dp[st[u] + 1] + x[u];
take[u] = 1;
return dp[st[u]];
};
int64_t lb = std::max(require[u], (int64_t) 0), rb = 1e18;
int64_t ans = -1;
while (lb <= rb) {
int64_t mb = (lb + rb) / 2;
if (do_dp(mb) >= 0) {
ans = mb;
rb = mb - 1;
} else {
lb = mb + 1;
}
}
auto prof = do_dp(ans);
if (ans != -1) s.emplace(ans, prof, u);
};
auto resolve = [&](int u) -> void {
std::vector<int> to_add;
for (int i = st[u]; i < en[u]; ) {
int v = who[i];
if (!take[v]) {
to_add.emplace_back(v);
i = en[v];
} else {
i++;
}
}
for (int v : to_add) {
find_good(v);
}
};
for (int i = 0; i < N; i++) {
if (p[i] == -1) {
auto dfs = [&](auto self, int u) -> void {
who[ti] = u;
st[u] = ti++;
for (int v : adj[u]) {
self(self, v);
}
en[u] = ti;
};
dfs(dfs, i);
find_good(i);
}
}
int64_t money = fund;
while (true) {
if (s.empty()) {
break;
}
auto [req, prof, u] = *(s.begin());
s.erase(s.begin());
if (req > money) {
break;
}
money += prof;
resolve(u);
}
std::cout << money- fund << nl;
}
