+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امیر از خواب بیدار شده اما هنوز کمی خسته است. او $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$ بهترین حالت است و پس از این که امیرمحمد ۹ دقیقه چرت می‌زند ۶- واحد انرژی دارد و پس از یک دقیقه انرژی‌اش ۷- می‌شود.

حل سؤال در بانک سؤالات