+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شرلوک هلمز در پی موری‌آرتی است و توانسته مکان اختفای او را کشف کند. خیابان‌های لندن شلوغ است و او برای رسیدن به موری‌آرتی باید از $n$ ساختمان که به هم متصل‌اند گذر کند تا او را در پس آخرین ساختمان بیابد. نحوه حرکت شرلوک بدین شرح است که در هر ثانیه می‌تواند حداکثر مسافت $k$ متر به بالا، پایین یا جلو حرکت کند تا به ساختمان بعدی برسد. در صورتی که مسافت مانده تا رسیدن به سقف ساختمان بعدی یا زمین کمتر از $k$ متر باشد، این مسافت باقیمانده را نیز در یک ثانیه طی می‌کند. همچنین در ابتدا شرلوک و موری‌آرتی روی زمین (در ارتفاع صفر) هستند. عرض هر ساختمان نیز برابر با $k$ متر است؛ به این معنا که شرلوک عرض هر ساختمان را در یک ثانیه طی می‌کند. شما باید بگویید حداقل زمان مورد نیاز شرلوک برای رسیدن به موری‌آرتی چقدر است؟ # ورودی ورودی شامل سه خط است. در خط اول، $k$ حداکثر مسافتی که هلمز می‌تواند در یک ثانیه طی کند، داده می‌شود. در خط دوم، عدد $n$ (تعداد ساختمان‌ها) آمده است. در خط سوم ورودی، $n$ عدد آمده که نشان‌دهنده ارتفاع ساختمان‌هاست. $$1 \le k, n, a_i \le 1000$$ # خروجی در خروجی مدت زمانی که طول می‌کشد تا هلمز در سریع ترین حالت به موری‌آرتی برسد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 3 2 13 8 ``` ## خروجی نمونه ۱ ``` 11 ``` <details class="yellow"> <summary> **توضیحات نمونه ۱** </summary> ---------- ![تصویر نمونه ۱](https://quera.org/qbox/view/FgYDFyM1CD/q1_1_1mit.jpg) + مقدار $k$ برابر ۴ است. به این معنی که شرلوک، در هر ثانیه حداکثر چهار متر حرکت می‌کند. اگر مسافت باقی‌مانده تا رسیدن به سقف ساختمان بعدی یا زمین کمتر از چهار متر باشد، آن مسافت را در ۱ ثانیه طی می‌کند تا در سریع ترین حالت به موری‌آرتی برسد. + در این مثال، هلمز از ساختمان اول که دو متر ارتفاع دارد، طی ۱ ثانیه بالا می‌رود. سپس در ۱ ثانیه عرض ساختمان اول را طی می‌کند. در ۳ ثانیه بعدی یازده متر دیگر از ساختمان دوم بالا می‌رود و ۱ ثانیه از روی آن عبور می‌کند. پس از آن در ۲ ثانیه پنج متر پایین می‌آید تا روی ساختمان سوم برسد و در ۱ ثانیه عرض آن را طی می‌کند. در نهایت هشت متر طول ساختمان سوم را در ۲ ثانیه پایین می‌آید و به موریاتی می‌رسد. بنابراین کل این مسیر $1 + 1 + 3 + 1 + 2 + 1 + 2 = 11$ ثانیه طول می‌کشد. </details> ## ورودی نمونه ۲ ``` 3 5 4 3 4 10 2 ``` ## خروجی نمونه ۲ ``` 15 ``` <details class="yellow"> <summary> **توضیحات نمونه ۲** </summary> ---------- ![تصویر نمونه ۲](https://quera.org/qbox/view/LBMq8JYNJp/q_1_2_2_4aqs.jpg) در این مثال، شرلوک در تلاش برای عبور از پنج ساختمان است و حداکثر مسافتی که شرلوک در یک ثانیه می‌تواند طی کند، برابر سه متر است. همانطور که در تصویر این مثال مشخص شده‌است، مقدار زمانی که نیاز است تا شرلوک تمام ساختمان‌ها را بپیماید، برابر تعداد بردار‌های قرمز در تصویر، یعنی ۱۵ ثانیه می‌شود. </details>

رقابت با زمان

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

شرلوک هلمز در پی موری‌آرتی است و توانسته مکان اختفای او را کشف کند. خیابان‌های لندن شلوغ است و او برای رسیدن به موری‌آرتی باید از $n$ ساختمان که به هم متصل‌اند گذر کند تا او را در پس آخرین ساختمان بیابد. نحوه حرکت شرلوک بدین شرح است که در هر ثانیه می‌تواند حداکثر مسافت $k$ متر به بالا، پایین یا جلو حرکت کند تا به ساختمان بعدی برسد. در صورتی که مسافت مانده تا رسیدن به سقف ساختمان بعدی یا زمین کمتر از $k$ متر باشد، این مسافت باقیمانده را نیز در یک ثانیه طی می‌کند. همچنین در ابتدا شرلوک و موری‌آرتی روی زمین (در ارتفاع صفر) هستند. عرض هر ساختمان نیز برابر با $k$ متر است؛ به این معنا که شرلوک عرض هر ساختمان را در یک ثانیه طی می‌کند. شما باید بگویید حداقل زمان مورد نیاز شرلوک برای رسیدن به موری‌آرتی چقدر است؟

ورودی🔗

ورودی شامل سه خط است. در خط اول، $k$ حداکثر مسافتی که هلمز می‌تواند در یک ثانیه طی کند، داده می‌شود. در خط دوم، عدد $n$ (تعداد ساختمان‌ها) آمده است. در خط سوم ورودی، $n$ عدد آمده که نشان‌دهنده ارتفاع ساختمان‌هاست. $1 \le k, n, a_i \le 1000$

خروجی🔗

در خروجی مدت زمانی که طول می‌کشد تا هلمز در سریع ترین حالت به موری‌آرتی برسد را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4
3
2 13 8

خروجی نمونه ۱🔗

توضیحات نمونه ۱

تصویر نمونه ۱

مقدار $k$ برابر ۴ است. به این معنی که شرلوک، در هر ثانیه حداکثر چهار متر حرکت می‌کند. اگر مسافت باقی‌مانده تا رسیدن به سقف ساختمان بعدی یا زمین کمتر از چهار متر باشد، آن مسافت را در ۱ ثانیه طی می‌کند تا در سریع ترین حالت به موری‌آرتی برسد.
در این مثال، هلمز از ساختمان اول که دو متر ارتفاع دارد، طی ۱ ثانیه بالا می‌رود. سپس در ۱ ثانیه عرض ساختمان اول را طی می‌کند. در ۳ ثانیه بعدی یازده متر دیگر از ساختمان دوم بالا می‌رود و ۱ ثانیه از روی آن عبور می‌کند. پس از آن در ۲ ثانیه پنج متر پایین می‌آید تا روی ساختمان سوم برسد و در ۱ ثانیه عرض آن را طی می‌کند. در نهایت هشت متر طول ساختمان سوم را در ۲ ثانیه پایین می‌آید و به موریاتی می‌رسد. بنابراین کل این مسیر $1 + 1 + 3 + 1 + 2 + 1 + 2 = 11$ ثانیه طول می‌کشد.

ورودی نمونه ۲🔗

3
5
4 3 4 10 2

خروجی نمونه ۲🔗

توضیحات نمونه ۲

تصویر نمونه ۲ در این مثال، شرلوک در تلاش برای عبور از پنج ساختمان است و حداکثر مسافتی که شرلوک در یک ثانیه می‌تواند طی کند، برابر سه متر است. همانطور که در تصویر این مثال مشخص شده‌است، مقدار زمانی که نیاز است تا شرلوک تمام ساختمان‌ها را بپیماید، برابر تعداد بردار‌های قرمز در تصویر، یعنی ۱۵ ثانیه می‌شود.