+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دوستان حنا برای هدیه تولد او $n$ شیرینی خریده‌اند و آن‌ها را پشت سر هم روی میز قرار داده‌اند. آن‌ها به حنا گفته‌اند که وزن شیرینی $i$ ام $w_i$ است (ممکن است وزن یک شیرینی منفی باشد!)‌. حالا حنا می‌خواهد یک بازه پشت سر هم از شیرینی‌ها را انتخاب کند و بخورد. اما از آنجایی که حنا رژیم دارد، مجموع وزن شیرینی‌هایی که می‌خورد، نمی‌تواند بیشتر از $W$ باشد. حنا که گیج شده‌است به شما روی آورده تا به او بیشترین وزن شیرینی که می‌تواند بخورد را بگویید. توجه کنید که حنا همیشه گزینه شیرینی نخوردن را دارد و جواب حداقل صفر هست. # ورودی در سطر اول عدد $n$ و $W$ به ترتیب آمده‌‌است. در سطر بعدی $\, w_1, w_2, \ldots, w_n $ به ترتیب آمده‌‌است. $$1 \leq n \leq 300 \, 000$$ $$ -10^9 \leq w_i\leq 10^9 $$ $$ 1 \leq W \leq 10^9$$ # خروجی بیشینه وزن شیرینی که حنا در مجموع می‌تواند بخورد را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 7 4 5 3 ``` ## خروجی نمونه ۱ ``` 5 ``` حنا تنها می‌تواند بازه $[2,2]$ را انتخاب کند. ## ورودی نمونه ۲ ``` 5 10 1 1 8 3 1 ``` ## خروجی نمونه ۲ ``` 10 ``` در اینجا می‌توانیم بازه $[1,3]$ را انتخاب کنیم. ## ورودی نمونه ۳ ``` 5 10 13 -1 7 -12 19 ``` ## خروجی نمونه ۳ ``` 7 ``` در اینجا می‌توانیم بازه $[1,4]$ را انتخاب کنیم. <details class="blue"> <summary> راهنمایی ۱ </summary> هر بازه را می‌توانید به چشم حاصل تفریق دو پیشوند نگاه کنید. به عبارت دیگر، اگر $sum_i$ را حاصل جمع وزن $i$ شیرینی اول در نظر بگیرید، وزن هر بازه‌ای از شیرینی‌ها را می‌توان به صورت حاصل تفریق دو تا از این متغیرها دید: $$sum_i,_j = sum_j - sum_i$$ سعی کنید با توجه به آرایه $sum$ سوال را حل کنید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> فرض کنید پایان بازه را فیکس کرده‌ایم (برای مثال عنصر $j$). حال اگر فرض کنیم متغیر $i$ نشان‌دهنده‌ی شروع بازه باشد. می‌توانیم کرانی برای $sum_j$ به دست آوریم. رابطه‌ای که در قسمت قبل گفتیم را می‌توان به این شکل بازنویسی کرد: $$sum_i = sum_j - sum_i,_j$$ از آن‌جایی که می‌دانیم حداکثری وزنی که حنا می‌تواند بخورد $W$ است، رابطه‌ی زیر برقرار است: $$sum_i <= sum_j - W$$ </details>