مسابقه | انرژی خور

انرژی خور


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

رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که یک فرد تنبل طماع است، نیاز به انرژی بیشتری برای خواب زمستانی دارد. از این رو به یک میوه‌فروشی رفته و می‌خواهد میوه بخورد تا انرژی بگیرد. او در ابتدا kk واحد انرژی دارد. میوه‌فروشی nn تا میوه دارد که با اعداد طبیعی نامگذاری شده‌اند و میوه‌ی i، مقدار aia_i انرژی به رادزینکا می‌دهد و مقدار bib_i انرژی از او می‌گیرد.(این انرژی به خاطر پوست کندن میوه است) پس دقت کنید که زمانی که رادزینکا می‌خواهد میوه‌ی ii را بخورد، باید حداقل به اندازه‌ی bib_i انرژی داشته باشد؛ زیرا این مقدار انرژی را باید صرف پوست کندن میوه کند و این مقدار از انرژی رادزینکا کم می‌شود. سپس او این میوه را می‌خورد و به انرژی‌اش aia_i تا اضافه می‌شود. رادزینکا می‌خواهد تعداد بزرگتر مساوی صفری از این میوه‌ها را انتخاب کرده و بخورد، طوری که در نهایت بیشترین انرژی را داشته باشد. به او بگویید که بیشترین انرژی که می‌تواند بدست بیاورد چقدر است.

ورودی🔗

در سطر اول ورودی دو عدد nn و kk آمده است که به ترتیب نمایانگر تعداد میوه‌ها و انرژی اولیه رادزینکا می‌باشد. سپس در هر یک از nn سطر بعدی یک میوه بدین صورت توصیف می‌شود:

دو عدد bib_i و aia_i آمده‌اند که عدد اول نمایانگر انرژی است که رادزینکا باید برای خوردن میوه مصرف کند و عدد دوم نمایانگر انرژی است که میوه به رادزینکا می‌دهد.

1n100 000 1 \le n \le 100\ 000 0ai,bi,k1 000 000 000 0\le a_i,b_i,k \le 1\ 000\ 000\ 000

خروجی🔗

خروجی باید شامل یک عدد باشد که برابر بیشترین انرژی است که رادزینکا می‌تواند با خوردن تعدادی میوه بدست بیاورد.

مثال🔗

ورودی نمونه ۱🔗

3 4
5 6
1 3
3 4
Plain text

خروجی نمونه ۱🔗

8
Plain text