+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در فینال جام جهانی 2022 هیجان به اوج خود رسیده است. تنها $n$ ثانیه از بازی باقی مانده، فرانسه از آرژانتین یک گل عقب است و امباپه تصمیم گرفته که دروازه تیم حریف را با شوت های پی در پی باز کند تا اختلاف گل دو تیم جبران شود. امباپه که دقیقا یک ثانیه قبل از شروع $n$ ثانیه پایانی شوتی بسیار بد و خارج از چارچوب دروازه زده، نزد امیرحسین، آنالیزور ارشد تیم فرانسه آمده تا در ادامه بازی به بهینه ترین شکل ممکن شوت هایش را بزند. در $i$مین ثانیه پس از شوت خجالت‌آور امباپه، انرژی او (که در ابتدا برابر 0 است) $a_i$ واحد افزایش می‌یابد، اما دقت کنید که ظرفیت ذخیره انرژی امباپه نامحدود نیست و اگر انرژی او به $m$ برسد ناگهان انرژی او تخلیه میشود و به صفر میرسد. به عبارتی اگر انرژی او در حال حاضر $e$ باشد و در ثانیه فعلی $a$ واحد به انرژی او اضافه شود، انرژی وی در نهایت برابر با $m$ $mod$ $(e + a)$ خواهد بود. این بازیکن محدودیت دیگری نیز دارد، از آنجا که دقایق زیادی از شروع بازی گذشته پاهای او دیگر توان زیادی ندارند و او نمی‌تواند دو شوت با فاصله زمانی کمتر از $k$ ثانیه بزند. امباپه می‌تواند در پایان هر ثانیه دلخواه یک شوت به سمت دروازه حریف بزند (در صورتی که شرط بالا نقض نشود). اگر زمان زدن شوت او $e$ واحد انرژی داشته باشد، این شوت $e$ واحد قدرت خواهد داشت و بعد از زدن شوت انرژی امباپه تخلیه و برابر با 0 میشود. **دقت کنید که دقیقا یک ثانیه قبل از شروع $n$ ثانیه پایانی امپابه یک شوت زده (و نمی‌تواند در $k-1$ ثانیه اول شوت دیگری بزند) و امیرحسین او را وادار میکند تا در ثانیه پایانی بازی هم یک شوت به سمت دروازه آرژانتین بزند. (بنابراین در ثانیه $n$ حتما یک شوت می‌زند)** از آنجا که امیرحسین شب گذشته را به خوبی نخوابیده از شما میخواهد تا به او و تیم فرانسه کمک کنید که بفهمند حداکثر جمع قدرت شوت های امباپه چقدر میتواند باشد.  # ورودی سطر اول ورودی، شامل سه عدد طبیعی $n$ , ثانیه های باقی مانده از بازی، $m$، ظرفیت انرژی امباپه، $k$، حداقل فاصله بین هر دو شوت است. $$1 \leq k \leq n \leq 3 * 10^5$$ $$1 \leq m \leq 10^9$$ در سطر بعدی، $n$ عدد می‌آید که عدد $i$م نشان دهنده ی $a_i$ است. $$1 \leq a_i \leq 10^9$$ # خروجی خروجی برنامه یک خط است و در آن باید بیشترین مقدار ممکن برای جمع قدرت شوت های امباپه را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 2 2 4 5 3 6 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 12 6 3 6 6 1 5 6 6 1 5 6 6 1 5 ``` ## خروجی نمونه ۲ ``` 6 ```