Tariflər
Rabitə operatoru bir birindən aylıq abonent ödəməsi və əlavə xidmətlər paketi ilə fərqlənən bir neçə limitsiz tarif planı hazırlamaq qərarına gəldi. Müştərilərlə iş menecerləri neçə VIP-müştəri şirkətinin rabitə xitmətlərinə pul ayıra biləcəyini müəyyən edə bildilər. İndi rabitə şirkəti hər bir müştəriyə özünün tarif planını təqdim etmək istəyir, lakin təəssüf ki, antimonopol siyasət üzrə komitə rabitə şirkətinə K-dan çox olmayan limitsiz tarif planına malik olmasına icazə veirir.
Şirkət menecerlərinə şirkətin gəlirlərini maksimuma çatdırmaları üçün K sayda tarif planı hazırlamalrına kömək edin.
Giriş verilənləri
Giriş faylının birinci sətrində iki ədəd, VIP-abonent şirkətlərinin N (1 ≤ N ≤ 100) sayı və K (1 ≤ K ≤ 100) tarif planlarının sayı. Sonra N sayda tam A_i (0 ≤ A_i ≤ 100000) ədədləri - i-ci abonentin rabitə üçün ayda ödəməyə hazır olduğu məbləğ verilir.
Çıxış verilənləri
Çıxış faylına abonent ödəmələrinin qiymətini ifadə edən artan sıra ilə K sayda natural ədəd verin. Abonent ödəməsinin qiyməti 1-dən az və 10^9-dan yüksək olmamalıdır.
Hesab edilir ki, hər bir abonentə abonent ödəməsinin maksimal olduğu, lakin A_i – dən yüksək olmadığı tarif planı təklif ediləcək və bu abonentə bu tarif planı ilə xidmət göstəriləcək.
Əgər belə bir tarif planı olmasa, şirkət tərəfindən abonentə xidmət göstərilməyəcək.
Şirkətin gəlirləri bütün abonent şirkətlərinin ödədikləri abonent ödəmələrinin cəmi kimi hesablanır.
Misalların şərhi
1-ci misal: Biz 1 ödəməyə hazır olan abonentə xidmət göstərməyəcəyik. 4 ödəməyə hazır olan abonenti biz birinci tarfif planına qoşacağıq. 5 ödəməyə hazır olan abonentləri – ikinciyə, 8 və 9 ödəməyə hazır olanları – üçüncüyə, 80-ni isə dördüncüyə qoşacağıq. Nəticədə şirkətin ümümi gəliri 4 + 5*4 + 8*2 + 80 = 120 olacaqdır.
2-ci misal: Hər bir abonenti öz tarifinə qoşuruq, 4-cü tarifi istifadə etmirik. Ümumi gəlir - 1+2+30=33 olacaqdır.
3-cü misal: Birinci və üçüncü abonentdən başqa bütün abonentləri birinci tarifə qoşuruq. Ümumi gəlir - 4*4 = 16 olacaqdır.
4-cü misal: Biz sıfır abonent ödəməsi tarifi edə bilmədiyimiz üçün 1-ci və 3-cü abonentlərə xidmət etməyəcəyik.