Тарифы
Оператор сотовой связи решил разработать несколько безлимитных тарифных планов, отличающихся между собой ежемесячной абонентской платой и набором дополнительных услуг. Менеджерам по работе с клиентами удалось выяснить, сколько каждый из VIP-абонентов компании готов тратить в месяц на услуги сотовой связи. Теперь сотовая компания хочет предложить каждому из абонентов свой тарифный план, но, к сожалению, комитет по антимонопольной политике разрешает сотовой компании иметь не более K безлимитных тарифных планов.
Помогите менеджерам компании разработать эти K тарифных планов, чтобы максимизировать доходы компании.
Входные данные
В первой строке входного файла записаны два числа: количество VIP-абонентов компании N (1 ≤ N ≤ 100) и количество тарифных планов K (1 ≤ K ≤ 100). Далее записано N целых чисел A_i - сумма, которую i-ый абонент готов тратить на связь в месяц (0 ≤ A_i ≤ 100000).
Выходные данные
Выведите в выходной файл K натуральных чисел - размеры абонентской платы в тарифных планах в порядке возрастания. Размер абонентской платы не должен быть меньше 1 и не может превышать 10^9.
Считается, что каждому абоненту будет предложен тарифный план, в котором абонентская плата максимально возможная, но не превышающая A_i, и этот абонент будет обслуживаться по этому тарифному плану. Если такого тарифного плана не окажется, абонент не будет обслуживаться компанией.
Доходы компании вычисляются как сумма абонентской платы, внесенной всеми абонентами компании.
Комментарии к примерам
1-й пример: Мы не будем обслуживать абонента, который готов платить 1. Абонента, который готов платить 4, мы подключим к первому тарифному плану. Абонентов, готовых платить 5 - ко второму, готовых платить 8 и 9 - к третьему, и готового платить 80 - к четвертому. Итого суммарный доход компании составит 4 + 5*4 + 8*2 + 80 = 120
2-й пример: Подключаем каждого абонента к своему тарифу, 4-й тариф не используем. Суммарный доход - 1+2+30=33
3-й пример: Подключаем всех, кроме первого и третьего абонентов, к единственному тарифу. Суммарный доход - 4*4 = 16
4-й пример: Поскольку мы не имеем права делать тариф с нулевой абонентской платой, то 1-го и 3-го абонентов обслуживать не будем.