Uzb Eng

0024. Magazin
: 2 c
: 64

Oybek akaning oilasi katta bolib, uning uch ogli va toqqizta nabirasi bor. Ularni hammasini taminlash lozim. Shuning uchun Oybek aka haftada bir marta magazinga boradi.
Bir kuni Oybek aka magazinga keldi va har bir k-chi tovar bepul nomli aksiya bolayotganini korib qoldi. Oybek aka aksiyani shartlari bilan tanishib chiqdi. Xaridor tovarlari bilan kassaga borib chek oladi. Masalan chekda n ta Tovar bolsa, u holda n/k eng arzoni unga tekinga tushadi.
Masalan, agar chekda 200, 100, 1000, 400 va 100 somli beshta tovar va k = 2 bolsa, u holda 100 somluk ikkita Tovar ham tekinga tushadi. Jami bolib xaridor 1600 som tolashi zarur.
Oybek aka tovarlarni oldi va kassaga keldi. Tushundiki, agarda olgan tovarlarni bir nechta cheklarga bolinsa kamroq pul tolanar ekan.
Oybek akaga olgan tovarlarini bir nechta cheklarga bolgan holda kammablag tolashiga yordam bering.
Misoldagi Oybek aka olgan tovarlarni ikkita chekga ajratamiz. Birinchi chekka 1000 va 400 somlisi, bunda 400 somlisi tekinga tushadi. Ikkinchi chekda esa 100 somli tovar tekinga tushadi. Demak jami bolib 1300 tolanadi.

:
Birinchi satrda ikkita butun son berilgan n, k (1 ≤ n ≤ 100 000, 2 ≤ k ≤ 100) Oybek aka sotib olgan tovarlar soni va har bir k-chi tovar bepul aksiyasini parametri.
Keyingi satr Oybek aka sotib olgan butun sonli n ta ai (1 ≤ ai ≤ 10 000) tovar narxlari.

:
Oybek aka tolagan minimum narxni chiqaring

5 2
200 100 1000 400 100
6 4
100 11 56 22 43 62
1300


251
:
: XII 2011


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.