#include <bits/stdc++.h>
#define el '\n'
#define FNAME "jobs"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}
void setup(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if (fopen(FNAME".inp","r")){
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
const int MAXN = 3e5 + 5;
const long long INF = (long long) 2e18 + 15092007;
int n;
long long S;
vector<pair<long long,int>> input;
vector<long long> w;
bool isLine=1;
void init(){
cin>>n>>S;
w.assign(n+1,0);
input.resize(n+1);
for (int i=1;i<=n;i++){
int x;
cin>>w[i]>>x;
if (x and x!=i-1) isLine=0;
input[i] = make_pair(w[i],x);
}
}
namespace Line{
vector<vector<long long>> chains;
int numChains;
void constructChains(){
vector<long long> curChain;
for (int i=1;i<=n;i++){
if (!input[i].second and !curChain.empty()){
chains.push_back(curChain);
curChain.clear();
}
curChain.push_back({input[i].first});
}
if (!curChain.empty()) chains.push_back(curChain);
numChains = chains.size();
}
struct Chain{
long long req;
long long gain;
int ID;
Chain(long long r,long long g,int id): req(r),gain(g),ID(id) {}
bool operator < (const Chain &other) const{
return req > other.req;
}
};
priority_queue<Chain> pq;
vector<int> ptr;
bool getNextSegment(int ID,long long &req,long long &gain){
long long minPre = INF;
long long pre = 0;
for (int &cid = ptr[ID];cid < (int)chains[ID].size();cid++){
pre += chains[ID][cid];
minimize(minPre,pre);
if (pre>=0){
req = max(0ll, -minPre);
gain = pre;
cid++;
return true;
}
}
return false;
}
void prepareRequirement(){
for (int i=0;i<numChains;i++){
long long req,gain;
if (getNextSegment(i,req,gain)){
pq.emplace(req,gain,i);
}
}
}
void solve(){
constructChains();
ptr.assign(numChains,0);
prepareRequirement();
long long totalGain=0;
while (!pq.empty()){
long long req = pq.top().req;
long long gain = pq.top().gain;
int ID = pq.top().ID;
pq.pop();
if (S + totalGain < req) break;
else{
totalGain += gain;
if (getNextSegment(ID,req,gain)){
pq.emplace(req,gain,ID);
}
}
}
cout<<totalGain;
exit(0);
}
};
namespace SubFinal{
vector<vector<int>> graph;
void constructTree(){
graph.resize(n+1);
for (int i=1;i<=n;i++){
graph[input[i].second].push_back(i);
}
}
struct Chain{
long long req,sum;
Chain(long long r,long long s): req(r), sum(s) {}
bool operator < (const Chain &other) const{
return req > other.req;
}
};
void merge(priority_queue<Chain> &large, priority_queue<Chain> &smol){
if (smol.size() > large.size()) large.swap(smol);
while (!smol.empty()){
large.emplace(smol.top());
smol.pop();
}
}
void combine(priority_queue<Chain> &large, Chain parent){
while (!large.empty()){
Chain top = large.top();
if (parent.sum <= 0){
large.pop();
long long newReq = max(parent.req,top.req - parent.sum);
parent = Chain(newReq,parent.sum + top.sum);
} else{
if (parent.req > top.req){
large.pop();
parent = Chain(parent.req,parent.sum + top.sum);
} else{
large.emplace(parent);
break;
}
}
}
if (large.empty()) large.emplace(parent);
if (large.size()==1 and large.top().sum <= 0) large.pop();
}
void dfs(int u,priority_queue<Chain> &large){
for (int v : graph[u]){
priority_queue<Chain> smol;
dfs(v,smol);
merge(large,smol);
}
combine(large,Chain(max(0ll,-w[u]),w[u]));
}
void solve(){
constructTree();
priority_queue<Chain> finalChain;
dfs(0,finalChain);
long long totalGain=0;
while (!finalChain.empty()){
long long req = finalChain.top().req;
long long sum = finalChain.top().sum;
finalChain.pop();
if (S + totalGain >= req){
totalGain += sum;
}
}
cout<<totalGain;
exit(0);
}
};
void sol(){
if (isLine) Line::solve();
SubFinal::solve();
}
int main(){
setup();
init();
sol();
}
