- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که یک فرد تنبل طماع است، نیاز به انرژی بیشتری برای خواب زمستانی دارد. از این رو به یک میوهفروشی رفته و میخواهد میوه بخورد تا انرژی بگیرد. او در ابتدا \(k\) واحد انرژی دارد. میوهفروشی \(n\) تا میوه دارد که با اعداد طبیعی نامگذاری شدهاند و میوهی i، مقدار \(a_i\) انرژی به رادزینکا میدهد و مقدار \(b_i\) انرژی از او میگیرد.(این انرژی به خاطر پوست کندن میوه است) پس دقت کنید که زمانی که رادزینکا میخواهد میوهی \(i\) را بخورد، باید حداقل به اندازهی \(b_i\) انرژی داشته باشد؛ زیرا این مقدار انرژی را باید صرف پوست کندن میوه کند و این مقدار از انرژی رادزینکا کم میشود. سپس او این میوه را میخورد و به انرژیاش \(a_i\) تا اضافه میشود. رادزینکا میخواهد تعداد بزرگتر مساوی صفری از این میوهها را انتخاب کرده و بخورد، طوری که در نهایت بیشترین انرژی را داشته باشد. به او بگویید که بیشترین انرژی که میتواند بدست بیاورد چقدر است.
ورودی
در سطر اول ورودی دو عدد \(n\) و \(k\) آمده است که به ترتیب نمایانگر تعداد میوهها و انرژی اولیه رادزینکا میباشد. سپس در هر یک از \(n\) سطر بعدی یک میوه بدین صورت توصیف میشود:
دو عدد \(b_i\) و \(a_i\) آمدهاند که عدد اول نمایانگر انرژی است که رادزینکا باید برای خوردن میوه مصرف کند و عدد دوم نمایانگر انرژی است که میوه به رادزینکا میدهد.
\[ 1 \le n \le 100\ 000 \] \[ 0\le a_i,b_i,k \le 1\ 000\ 000\ 000 \]
خروجی
خروجی باید شامل یک عدد باشد که برابر بیشترین انرژی است که رادزینکا میتواند با خوردن تعدادی میوه بدست بیاورد.
مثال
ورودی نمونه ۱
3 4
5 6
1 3
3 4
خروجی نمونه ۱
8