#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 3e5 + 5;
int n, x[lim], p[lim];
ll money;
namespace sub1{
void solve(){
vector<vector<int>>g(n + 1);
for(int i = 1; i <= n; i++){
g[p[i]].push_back(i);
}
x[0] = 0;
function<ll(int)>dfs;
dfs = [&] (int s){
ll sum = 0;
for(int& d : g[s]){
sum += dfs(d);
}
return max(0LL, sum + x[s]);
};
cout << dfs(0);
}
}
namespace sub2{
bool check_subtask(){
if(n > 2000){
return false;
}
for(int i = 1; i <= n; i++){
if(p[i] != 0 && p[i] != i - 1){
return false;
}
}
return true;
}
struct Data{
int start, end;
ll need, profit;
Data(){}
Data(int _start, int _end, ll _need, ll _profit) : start(_start), end(_end), need(_need), profit(_profit) {}
friend bool operator <(const Data a, const Data b){
return a.need > b.need || (a.need == b.need && a.profit < b.profit);
}
};
void solve(){
priority_queue<Data>pq;
vector<bool>ban_start(n + 1, false);
vector<int>left(n + 1);
p[n + 1] = 0;
for(int i = 1; i <= n; i++){
left[i] = p[i] == 0 ? i : left[i - 1];
if(p[i + 1] == 0){
ll need = 0, profit = 0;
for(int j = left[i]; j <= i; j++){
maximize(need, -(profit += x[j]));
if(profit > 0){
pq.push(Data(left[i], j, need, profit));
}
}
}
}
ll init_money = money;
while(!pq.empty()){
auto [start, end, need, profit] = pq.top();
pq.pop();
if(ban_start[start]){
continue;
}
if(need > money){
break;
}
money += profit;
ban_start[start] = true;
need = profit = 0;
for(int i = end + 1; i <= n && left[i] == left[start]; i++){
maximize(need, -(profit += x[i]));
if(profit > 0){
pq.push(Data(end + 1, i, need, profit));
}
}
}
cout << money - init_money;
}
}
namespace sub3{
bool check_subtask(){
for(int i = 1; i <= n; i++){
if(p[i] != 0 && p[i] != i - 1){
return false;
}
}
return true;
}
struct Node{
ll pmin, pmax, sum;
Node(){
pmin = pmax = sum = 0;
}
};
int left[lim];
Node st[lim << 2];
Node merge(Node a, Node b){
Node c;
c.pmin = min(a.pmin, a.sum + b.pmin);
c.pmax = max(a.pmax, a.sum + b.pmax);
c.sum = a.sum + b.sum;
return c;
}
void build(int id, int l, int r){
if(l == r){
st[id].pmin = min(0LL, st[id].sum = x[l]);
st[id].pmax = max(0, x[l]);
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
Node get(int id, int l, int r, int u, int v){
if(l > v || r < u){
return Node();
}
if(u <= l && v >= r){
return st[id];
}
int m = (l + r) >> 1;
return merge(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
struct Data{
int start, end;
ll need, profit;
Data(){}
Data(int _start, int _end, ll _need, ll _profit) : start(_start), end(_end), need(_need), profit(_profit) {}
friend bool operator <(const Data a, const Data b){
return a.need > b.need || (a.need == b.need && a.profit < b.profit);
}
};
priority_queue<Data>pq;
void find_and_push(int i){
int low = i, high = n, end = -1;
Node ans;
while(low <= high){
int mid = (low + high) >> 1;
if(left[mid] != left[i]){
high = mid - 1;
}
else{
Node x = get(1, 1, n, i, mid);
if(x.pmax < 1){
low = mid + 1;
}
else{
ans = x;
high = (end = mid) - 1;
}
}
}
if(end != -1){
pq.push(Data(i, end, -ans.pmin, ans.pmax));
}
}
void solve(){
build(1, 1, n);
for(int i = 1; i <= n; i++){
left[i] = p[i] == 0 ? i : left[i - 1];
}
for(int i = 1; i <= n; i++){
if(p[i] == 0){
find_and_push(i);
}
}
ll init_money = money;
while(!pq.empty()){
auto [start, end, need, profit] = pq.top();
pq.pop();
if(need > money){
break;
}
money += profit;
if(end < n && left[end + 1] == left[start]){
find_and_push(end + 1);
}
}
cout << money - init_money;
}
}
namespace sub45{
int lab[lim];
ll profit[lim], need[lim];
int find_set(int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
}
void solve(){
profit[lab[0] = 0] = money;
for(int i = 1; i <= n; i++){
need[lab[i] = i] = min(0LL, profit[i] = x[i]);
}
priority_queue<pair<ll, int>>pq;
for(int i = 1; i <= n; i++){
if(x[i] > 0){
pq.push(make_pair(need[i], i));
}
}
while(!pq.empty()){
auto [foo, i] = pq.top();
pq.pop();
if(i == find_set(i)){
int j = find_set(lab[i] = p[i]);
ll new_need = min(need[j], profit[j] + need[i]);
if(new_need < 0 && j == 0){
break;
}
profit[j] += profit[i];
need[j] = new_need;
if(j > 0 && profit[j] > 0){
pq.push(make_pair(need[j], j));
}
}
}
cout << profit[0] - money;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> money;
for(int i = 1; i <= n; i++){
cin >> x[i] >> p[i];
}
if(money == ll(1e18)){
sub1::solve();
}
else if(sub2::check_subtask()){
sub2::solve();
}
else if(sub3::check_subtask()){
sub3::solve();
}
else{
sub45::solve();
}
}
