• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

رادزینکا دوبرامیل ویچشسلافوویچ (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