Тарифи#2212
Оператор мобільного зв'язку вирішив створити декілька безлімітних тарифних планів, кожен з різною щомісячною абонентською платою та додатковими сервісами. Менеджери з роботи з клієнтами визначили, скільки кожен VIP-абонент готовий витрачати на мобільні послуги на місяць. Тепер компанія хоче запропонувати кожному абоненту персоналізований тарифний план. Проте, відповідно до антимонопольного регулювання, компанія може запропонувати не більше ніж безлімітних тарифних планів.
Допоможіть менеджерам компанії розробити тарифних планів так, щоб максимізувати прибуток компанії.
У першому рядку задано два цілі числа: кількість VIP-абонентів (1 \leq N \leq 100) та кількість тарифних планів (1 \leq K \leq 100). Далі наведено цілих чисел A_i (0 \leq A_i \leq 100000), де A_i — це сума, яку -ий абонент готовий витратити на послуги зв'язку на місяць.
Виведіть додатних цілих чисел у зростаючому порядку — абонентську плату для кожного тарифного плану. Кожна плата має бути не менше і не більше 10^9.
Кожен абонент буде підключений до тарифного плану з максимально можливою вартістю, що не перевищує A_i. Якщо такого тарифного плану немає, абонент не буде обслуговуватись компанією.
Прибуток компанії — це сума абонентських плат, сплачених усіма абонентами.
Коментарі до прикладів
Приклад 1: Абонент, який готовий платити , не буде обслуговуватись. Абонент, який готовий платити , підключається до першого тарифу. Готові платити — до другого, готові і — до третього, а абонент, готовий платити , — до четвертого. Загальний прибуток: 4 + 5 \cdot 4 + 8 \cdot 2 + 80 = 120.
Приклад 2: Кожен абонент підключений до власного тарифу; четвертий тариф не використовується. Загальний прибуток 1 + 2 + 30 = 33.
Приклад 3: Усі абоненти, крім першого та третього, підключені до одного тарифу. Загальний прибуток 4 \cdot 4 = 16.
Приклад 4: Оскільки тариф зі ставкою не дозволяється, перший і третій абоненти не будуть обслуговуватись.
Приклад 1