#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
const long long inf = 2e18;
int n;
long long base, res;
// Sửa: Dùng vector để giữ thứ tự, thêm mảng merged
vector<int> chosen[maxn];
bool merged[maxn];
pair<long long, int> a[maxn];
vector<int> adj[maxn];
priority_queue<pair<long long, int>> posi, nega;
struct sct{
long long cost, prof;
inline sct(){
cost = prof = 0;
}
} dp[maxn];
inline void DFS(int u){
if (a[u].first >= 0){
dp[u].cost = 0;
dp[u].prof = a[u].first;
// Node dương không cần gộp con để "cứu" nó, chỉ cần duyệt tiếp
for (int v : adj[u])
DFS(v);
return;
}
else{
dp[u].cost = dp[u].prof = a[u].first;
vector<int> vec;
for (int v : adj[u]){
DFS(v);
// Chỉ xem xét gộp những node con không bị loại bỏ (-inf)
if (dp[v].cost != -inf)
vec.push_back(v);
}
// Sắp xếp con nào "rẻ" nhất (ít âm nhất) chạy trước
sort(vec.begin(), vec.end(), [](int i, int j){
return dp[i].cost > dp[j].cost;
});
for (int v : vec){
// Logic tính cost: Min của cost hiện tại VÀ (profit hiện tại + cost của con tiếp theo)
dp[u].cost = min(dp[u].cost, dp[u].prof + dp[v].cost);
dp[u].prof += dp[v].prof;
// Lưu lại con được chọn vào vector theo đúng thứ tự
chosen[u].push_back(v);
merged[v] = true; // Đánh dấu đã gộp
if (dp[u].prof > 0) break;
}
}
// Nếu gộp xong vẫn lỗ vốn (net negative) thì coi như nhánh này bỏ đi (vì mục tiêu là max profit)
if (dp[u].prof <= 0){
dp[u].cost = dp[u].prof = -inf;
chosen[u].clear(); // Xóa chosen để tránh update nhầm
}
}
// Hàm update sửa đổi: Chạy u, sau đó chạy các con trong chosen, và mở khóa các con khác
inline void execute_job(int u){
res += a[u].first;
// 1. Mở khóa những con KHÔNG được gộp (nằm ngoài block)
for (int v : adj[u]){
if (!merged[v]){
if (a[v].first >= 0)
posi.push({a[v].first, v});
else if (dp[v].cost != -inf)
nega.push({dp[v].cost, v});
}
}
// 2. Chạy tiếp các con ĐÃ gộp theo đúng thứ tự đã tính trong DFS
for (int v : chosen[u]){
execute_job(v);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> base;
for (int i = 1; i <= n; ++i){
cin >> a[i].first >> a[i].second;
if (a[i].second != 0)
adj[a[i].second].push_back(i);
}
// DFS từ các node gốc (p=0)
for (int i = 1; i <= n; ++i) if (a[i].second == 0){
DFS(i);
// Chỉ push vào hàng đợi những node chưa bị gộp (đây là các root block)
if (!merged[i]) {
if (a[i].first >= 0)
posi.push({a[i].first, i});
else if (dp[i].cost != -inf)
nega.push({dp[i].cost, i});
}
}
while(!posi.empty() || !nega.empty()){
if (!posi.empty()){
auto [cost, u] = posi.top();
posi.pop();
// Node dương luôn an toàn để lấy
execute_job(u);
}
else if (!nega.empty()){
auto [cost, u] = nega.top();
nega.pop();
// Kiểm tra xem có đủ tiền để chịu được mức sụt giảm (cost) thấp nhất của block này không
// base + res là số tiền hiện tại. cost là số âm.
if (base + res + cost < 0)
break;
execute_job(u);
}
}
cout << res;
return 0;
}
