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

---

امیر از خواب بیدار شده اما هنوز کمی خسته است. او $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$ بهترین حالت است و پس از این که امیرمحمد ۹ دقیقه چرت می‌زند ۶- واحد انرژی دارد و پس از یک دقیقه انرژی‌اش ۷- می‌شود.