ŠIOM — Liftas

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_2et_liftas_jau.in

Rezultatų failas: lmio_2018_2et_liftas_jau.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Liftas

Rusnė gyvena $N$ -ame aukšte ir kasdien naudojasi pastate įrengtu liftu. Vieną dieną ji nusprendė, kad, sveikatos labui, ji liftu nesikels daugiau negu $K$ aukštų. Tačiau aukštai šiame pastate yra skirtingų aukščių (matuojamų laiptų skaičiumi), o Rusnė yra gudri ir visgi nori lipti kuo mažiau laiptų savo kojomis.

Užduotis

Jums duoti visų pastato aukštų aukščiai. Raskite, kiek mažiausiai laiptų Rusnė turės lipti savo kojomis, jeigu liftu ji gali važiuoti tik $K$ aukštų. (Rusnė gali įlipti ir išlipti iš lifto kiek nori kartų.)

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai: $N$ – kuriame aukšte gyvena Rusnė, ir $K$ – kiek aukštų ji nusprendė keltis liftu.

Toliau seka $N$ eilučių. Kiekvienoje eilutėje įrašyta po vieną skaičių $a_i$ – aukšto $i$ aukštį, matuojamą laiptais (pradedant nuo pirmo aukšto).

Pastato aukštai yra numeruojami nuo 0 iki $N$ . 0-inis aukštas yra žemės lygyje. Liftą galima išsikviesti kiekviename aukšte.

Rezultatai

Išveskite vieną sveikajį skaičių – kiek mažiausiai laiptų Rusnė turės lipti grįždama namo.

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paaiškinimas
5 3 19 20 20 20 14	33	Šiuo atveju Rusnei apsimoka lipti iki pirmojo aukšto pėsčiomis, tada keltis iki ketvirtojo aukšto liftu, ir paskutinė aukštą vėl užlipti pėsčiomis.

Ribojimai