U Bajtogradu se otvara novi tržni centar. Na otvaranje je doshlo n stanovnika Bajtograda. Tržni centar je ogroman
i ima više spratova. Svaki sprat ima drugačije prodavnice. Ljudi su upoznati koje prodavnice su na kom spratu,
pa je svako u skladu sa tim odlučio koji sprat će prvo da obiđe.
Međutim, vlasnici tržnog centra nisu očekivali toliki broj ljudi, pa su postavili samo jedan lift. Srećom, taj lift je
iz nove serije V2512 super-brzih liftova. Liftu je potrebna samo jedna sekunda da se popne ili spusti za jedan sprat.
U lift može da stane najviše c osoba.
Lift, kao i svi ljudi, na početku se nalaze u prizemlju - na spratu 0. Ako je poznato na koji sprat svaka osoba želi
da ode i ako je vreme zaustavljanja lifta zanemarljivo, odredite koliko je minimalno vreme potrebno
da sve osobe odu na željeni sprat.
Ulaz:
(Ulazni podaci se nalaze u datoteci lift.in.)
U ulaznoj datoteci se u prvom redu nalaze dva broja n i c (1 ≤ n, c ≤ 1.000),
broj ljudi i kapacitet lifta, respektivno. U sledećem redu nalazi se n brojeva iz intervala [0, 100.000],
koji predstavljaju na koji sprat svaka od n osoba želi da ode.
Izlaz:
(Izlazne podatke upisati u datoteku lift.out)
U prvom i jedinom redu izlazne datoteke ispisati minimalno vreme u sekundama potrebno da svaka osoba stigne na željeni sprat.
Primer:
lift.in
|
|
lift.out
|
4 2
1 2 4 2
|
|
8
|
Objašnjenje.
U lift uđu dve osobe koje žele da idu na 2. sprat. Lift potroši 4 sekunde da se popne do 2. sprata i vrati do prizemlja.
Zatim u lift uđu osoba koja ide na 1. sprat i osoba koja ide na 4. sprat. Lift se popne do 1. sprata na kom izađe
jedna osoba i zatim nastavi do 4. sprata gde izađe i druga. Za to je potrebno još 4 sekunde, pa je ukupno vreme 8 sekundi.
Primer:
lift.in
|
|
lift.out
|
5 3
6 4 6 4 2
|
|
14
|
Objašnjenje.
U lift uđu tri osobe koje idu na spratove 2, 4 i 4. Lift potroši 4 sekunde da ostavi osobe na željenim spratovima i 4 sekunde
da se vrati na prizemlje. Zatim u lift uđu dve osobe koje idu na 6. sprat, te lift potroši još 6 sekundi da dođe do 6. sprata.
Ukupno vreme je 14 sekundi.