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

---

امیر از خواب بیدار شده اما هنوز کمی خسته است. او \(T\) دقیقه دیگر فرصت استراحت دارد و چون خسته است تصمیم می‌گیرد کمی چرت بزند.

هر چرت دارای دو مشخصه \(t_i\) و \(e_i\) است که به ترتیب مدت زمان چرت و مقدار انرژی دریافتی از چرت را مشخص می‌کند؛ توجه کنید که ممکن است او بعد از یک چرت خسته‌تر باشد یا به عبارت دیگر، \(e_i\) صفر و یا حتی منفی باشد!

هم‌چنین امیر به ازای هر دقیقه از \(T\) دقیقه که چرت نمی‌زند، یک واحد از انرژی‌اش کم می‌شود و در زمان صفر هم، صفر واحد انرژی دارد.

امیر می‌خواهد یک \(i\) انتخاب کند و به ترتیب چرت‌های \(1\) تا \(i\) را بزند بطوری که در دقیقه‌ی \(T\) همه‌ی چرت‌هایش تمام شده باشد و بیدار باشد؛ حال شما به او بگویید که با این شرایط در زمان \(T\)، حداکثر چقدر انرژی می‌تواند داشته باشد.

توجه کنید که \(i\) می‌تواند صفر باشد و به ازای \(i\) انتخابی جمع چرت‌ها باید کم‌تر مساوی \(T\) باشد.

ورودی

خط اول ورودی شامل دو عدد \(n\) و \(T\) است. سپس در \(n\) خط دیگر ورودی، در هر خط به ترتیب دو عدد \(t_i\) و \(e_i\) می‌آیند.

\[1 \le n \le 10^5\] \[1 \le T \le 10^9\] \[1 \le t_i \le 10^4\] \[-10^4 \le e_i \le 10^4\]

خروجی

بیشینه انرژی امیر را در زمان \(T\) چاپ کنید. توجه کنید که این عدد ممکن است منفی باشد.

مثال

ورودی نمونه ۱

3 5
1 1
2 3
1 -2

خروجی نمونه ۱

2

در این مثال امیر، \(i\) را ۲ انتخاب می‌کند و چرت‌های ۱ و ۲ را می‌زند؛ بنابراین بعد از ۳ دقیقه (که هر دو چرتش تمام شده)، ۴ واحد انرژی دارد؛ سپس دو دقیقه چرت نمی‌زند و ۲ واحد انرژی‌اش کم می‌شود؛ بنابراین در نهایت ۲ واحد انرژی دارد.

ورودی نمونه ۲

2 10
5 -3
4 -3

خروجی نمونه ۲

-7

در این مثال هم \(i = 2\) بهترین حالت است و پس از این که امیرمحمد ۹ دقیقه چرت می‌زند ۶- واحد انرژی دارد و پس از یک دقیقه انرژی‌اش ۷- می‌شود.