Školska razina 2018 / Osnovna škola (7. razred) - 3. zadatak

U trgovini igračaka u tijeku je akcija kojom se želi privući nove kupce. Ideja je da kupac, kada dođe na blagajnu, sve igračke koje je odabrao podijeli u što je više moguće skupina s po točno \(K\) igračaka. Trgovina će tada iz svake skupine odabrati najjeftiniju igračku i nju pokloniti kupcu dok će preostale igračke kupac platiti onoliko koliko koštaju. Igračke koje se nisu mogle rasporediti u skupinu ne ulaze u akciju i kupac ih plaća po njihovoj cijeni.

Kevin je odabrao \(N\) igračaka i sada ih želi podijeliti u skupine po \(K\) ali tako da ukupni plaćeni iznos bude najmanji mogući. Pomozi Kevinu rješiti ovaj problem i ispiši koliko je na kraju platio svoje igračke.

ULAZNI PODACI

U prvom retku nalazi se prirodan broj \(N\) \((1 \leq N \leq 15)\), broj iz teksta zadatka.

U drugom retku nalazi se prirodan broj \(K\) \((1 \leq K \leq 15)\), broj iz teksta zadatka.

U sljedećih N redaka nalazi se po jedan prirodan broj \(Ci\) \((1 \leq Ci \leq 20)\), cijena i-te odabrane igračke.

IZLAZNI PODACI

U jednom retku treba ispisati traženi broj iz teksta zadatka.

PRIMJERI TEST PODATAKA

Ulaz

3
3
1
3
2

Izlaz

5

Ulaz

4
3
2
4
3
5

Izlaz

11

Opis drugog primjera: Kevin mora 4 igračke podijeliti u skupine s po točno 3 igračke. To može učiniti na sljedeće načine (prekrižena je cijena poklonjene igračke): (2+4+3)+5=12; (2+4+5)+3 =12; (2+3+5)+4=12 i (4+3+5)+2=11.

Ulaz

11
3
5
6
9
7
1
2
5
4
8
9
3

Izlaz

43