/* See BOI editorial for Idea. We just use a multiset to store instead of a set, since there may be duplicates. Note: Usually, you should try to avoid multisets, however, insertion is only O(log m). Only .count() is running in O(log m + k), so we are safe here. Removal via keys is O(log m + k) too, however, only amortized only O(log m). */ #include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define tiii tuple<int,int,int> int mod = 1e9+7; int INF = numeric_limits<int>::max()/32; vector<vector<int>> adj; vector<int>val; vector<multiset<pii>> order; void DFS(int v){ for(auto u : adj[v]){ DFS(u); } for(auto u : adj[v]){ if(order[u].size() > order[v].size()) swap(order[u],order[v]); for(auto b : order[u]){ order[v].insert(b); } } pii b = {max(0LL,-val[v]), val[v]}; while(order[v].size() && ( (b.first >= (*(order[v].begin())).first) || b.second <= 0)){ int m,s; tie(m,s) = *order[v].begin(); order[v].erase(order[v].begin()); b = {max(b.first,m-b.second), b.second+s}; } if(b.second >= 0) order[v].insert(b); } int32_t main(){ int n, s; cin >> n >> s; int os = s; val.resize(n+1); adj.resize(n+1); order.resize(n+1); vector<tiii> nodes; priority_queue<tiii, vector<tiii>,greater<tiii>> pq; int c = 0; int mi = 0; int req = -1; vector<int> tba; for(int i = 1; i <= n; i++){ cin >> val[i]; int p; cin >> p; adj[p].push_back(i); } DFS(0); int tot = 0; vector<pii> blocks(order[0].begin(),order[0].end()); for(auto [mini, profit] : blocks){ assert(profit >= 0); if(s < mini) break; s += profit; } cout << s-os << "\n"; }