#include #include #include #include #include #include #define ll long long using namespace std; typedef struct tga{ ll s,t,y,m; } tga; int main(){ ll N,C,V,numCount=0,ansTime=-1; cin>>N>>C>>V; vector st,yst,mst,ist; vector v(V); vector goty(V+1,0),gotm(V+1,0); for(ll i=0;i>v[i].s; } for(ll i=0;i>v[i].t; } for(ll i=0;i>v[i].y; } for(ll i=0;i>v[i].m; } sort(v.begin(),v.end(), [](const tga& a,const tga& b) {return a.t< b.t;}); st.push_back(N); for(ll i=0;;i++){ if(st[st.size()-1]==v[i].t){ yst.push_back(v[i].y); mst.push_back(v[i].m); if(Cgotm[i]&& accumulate(yst.begin(),yst.end(),0)>goty[i]){ yst.pop_back(); mst.pop_back(); continue; } gotm[i]=accumulate(mst.begin(),mst.end(),0); goty[i]=accumulate(yst.begin(),yst.end(),0); st.push_back(v[i].s); ist.push_back(i); i=-1; } else if(st[st.size()-1]==1){ if(C>=accumulate(yst.begin(),yst.end(),0)){ if(ansTime==-1){ ansTime=accumulate(mst.begin(),mst.end(),0); } else{ if(ansTime>accumulate(mst.begin(),mst.end(),0)) ansTime=accumulate(mst.begin(),mst.end(),0); } } numCount++; st.pop_back(); i=ist[ist.size()-1]; ist.pop_back(); yst.pop_back(); mst.pop_back(); } else if(v[i].t>st[st.size()-1]){ if(st[st.size()-1]==N) break; st.pop_back(); i=ist[ist.size()-1]; ist.pop_back(); yst.pop_back(); mst.pop_back(); } } printf("%lld",ansTime); }