این سوال یه‌کم خودمونیه!


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

سل‍ام، من علی‌رضا افشار هستم، تکنیکال لید تیم Shopping-Operation دیجی‌کالا!

امسال تصمیم گرفتم پس‌اندازم رو به میزان m تومن افزایش بدم تا چند سال بعد بتونم یه زندگی بهتر داشته‌باشم. برای این کار تصمیم گرفتم تا با گرفتن وام از شرکت، تو چند فرصت سرمایه‌گذاری در بازار رمزارزها (Cryptocurrency) شرکت کنم تا با سودی که از این فرصت‌ها بدست میاد، بتونم وامی که گرفتم رو پس بدم و یک سرمایه‌ای هم برای خودم جمع کنم. البته تو هر فرصت فقط یکبار میشه سرمایه‌گذاری کرد و سودش از روز بعد حساب میشه.

تو لیست n فرصتی که پیدا کردم، هزینه فرصت ii-ام، cic_i تومنه و سودی که از این فرصت بدست میاد، pip_i تومن. به من کمک کنید تا بتونم محاسبه کنم با سرمایه‌گذاری تو فرصت‌های درست، کمترین تعداد روز ممکن برای پس دادن وام چقدره. دم شما هم گرم :)

ورودی🔗

در خط اول ورودی دو عدد طبیعی nn و mm با فاصله از هم آمده است. 1n1051 \le n \le 10^5 1m1091 \le m \le 10^9 در nn خط بعدی در هر خط دو عدد آمده که به ترتیب pip_i و cic_i را نشان می‌دهد 1pi,ci1091 \le p_i, c_i \le 10^9

خروجی🔗

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

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

2 5
4 10
10 15
Plain text

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

2
Plain text

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

4 10
1 8
3 12
4 17
10 100
Plain text

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

6
Plain text

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

3 5
4 1
9 10
6 3
Plain text

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

1
Plain text