Tariflər#2212
Bir mobil operator bir neçə limitsiz tarif planı yaratmağa qərar verib, onların hər birinin aylıq abunə haqqı və əlavə xidmətləri fərqlidir. Müştəri münasibətləri menecerləri hər bir VIP abunəçinin mobil xidmətlərə ayda nə qədər xərcləməyə hazır olduğunu müəyyən ediblər. İndi şirkət hər abunəçiyə fərdi tarif təklifi vermək istəyir. Lakin, rəqabətə qarşı qanunvericiliyə görə, şirkət ən çox K limitsiz tarif planı təklif edə bilər.
Şirkətin menecerlərinə K tarif planı hazırlamaqda kömək edin ki, şirkətin gəliri maksimum olsun.
Birinci sətrdə iki tam ədəd — VIP abunəçilərin sayı N (1 \leq N \leq 100) və tarif planlarının sayı K (1 \leq K \leq 100) verilir. Sonraki sətirdə isə N tam ədəd A_i (0 \leq A_i \leq 100000) verilib, burada A_i -ci abunəçinin rabitə xidmətləri üçün ayda xərcləməyə hazır olduğu məbləğdir.
K ədəd müsbət tam ədəd verin — tarif planlarının abunə haqlarını artan ardıcıllıqla çap edin. Hər bir abunə haqqı ən azı , ən çoxu isə 10^9 olmalıdır.
Hər bir abunəçi ona uyğun olan ən yüksək, lakin A_i-dən artıq olmayan abunə haqqı olan tarif planına təyin edilir. Əgər belə tarif yoxdursa, abunəçi şirkət tərəfindən xidmət edilməyəcək.
Şirkətin gəliri bütün abunəçilərin ödədiyi abunə haqlarının cəminə bərabərdir.
Nümunə izahları
Nümunə 1: ödəməyə hazır olan abunəçi xidmət ala bilmir. ödəməyə hazır abunəçi ilk plana təyin olunur. ödəməyə hazır abunəçilər ikinci plana təyin olunur, və ödəməyə hazır olanlar üçüncü plana, ödəməyə hazır olan isə dördüncü plana təyin olunur. Ümumi gəlir 4 + 5 \cdot 4 + 8 \cdot 2 + 80 = 120.
Nümunə 2: Hər abunəçi özünə uyğun plana təyin olunur; dördüncü plan istifadə olunmur. Ümumi gəlir 1 + 2 + 30 = 33.
Nümunə 3: Bütün abunəçilərdən yalnız birinci və üçüncü xidmət almır. Ümumi gəlir 4 \cdot 4 = 16.
Nümunə 4: Çünki abunə haqqı sıfır ola bilməz, birinci və üçüncü abunəçilər xidmət ala bilmir.
Nümunə 1