DRŽAVNO NATJECANJE 2013. – Drugi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 2. zadatak

Poljoprivrednik Mirko upravo je kupio velik broj predivnih konja različitih pasmina, te se priprema za veliku paradu u njemu mrskom susjednom selu.

Kako bi njegov ulaz u mrsko mu selo bio što spektakularniji odlučio je konje poredati u redove.

U svim redovima treba se nalaziti jednak broj konja te svi konji u istom redu moraju biti iste pasmine.

Također, kako su uske kolone neugledne, Mirko želi da u svakom redu bude barem K konja.

Tužna srca shvatio je da zbog ovih uvjeta možda neće moći povesti sve svoje konje pa mu treba vaša pomoć da ih povede što više.

Napišite program koji će na temelju podataka o ukupnom broju konja pojedine pasmine na raspolaganju te broja K odrediti najveći broj konja koje Mirko može poredati u redove s jednakim brojem konja tako da niti jedan red ne sadrži konje različitih pasmina.

Dodatno, u svakom redu broj konja mora biti jednak barem K.

Ulazni podaci

U prvom retku ulaza nalaze se prirodni brojevi N i K (1 ≤ N ≤ 1 000 000, 2 ≤ K ≤ N), broj različitih pasmina konja te najmanja dozvoljena veličina pojedinog reda.

U drugom retku ulaza nalazi se N prirodnih brojeva Pi (1 ≤ Pi ≤ 1 000 000), broj konja i-te pasmine.

Izlazni podaci

U prvi i jedini redak izlaza potrebno je ispisati najveći mogući ukupni broj konja koje Mirko može povesti sa sobom po pravilima navedenim u tekstu zadatka.

Primjeri test podataka

Ulaz

3 2
1 2 3

Izlaz

4

Ulaz

5 2
3 4 4 3 3

Izlaz

15

Ulaz

7 3
1 4 9 3 8 5 16

Izlaz

40