Задача №114200. Будни миллиардеров
Труд младшего преподавателя на сборах по подготовке к региональному этапу очень тяжел, хоть и приятен. Но, конечно, отдыхать еще лучше.
Именно поэтому в этом году Толя поехал на Гран-при Формулы 1 в Сочи. Он хорошо подготовился и узнал, что на гонку планируют поехать целых n человек, что несомненно больше, чем VIP абонентов одного известного оператора сотовой связи. Также известно, что \(i\)-й из них готов потратить на билет не более \(A_i\) рублей.
В рекламном буклете говорится, что в этом году вокруг трассы построили \(k\) трибун, вмещающих в себя неограниченное кол-во зрителей, а цены на билеты на каждую из трибун различные натуральные числа, не превышающие \(10^9\).
Толик много раз был на сборах и не раз ходил к психологу, от которого узнал, что человек считает цену показателем качества.
Из этого он сделал вывод, что каждый зритель купит себе наиболее дорогой билет, который сможет себе позволить (или не купит никакой из них).
Поскольку Толик очень любит решать разные задачи, он решил узнать, какие цены на билеты надо выбрать, чтобы организаторы гонки заработали как можно больше денег.
Толик смог решить эту задачу, а сможете ли вы?
В первой строке входного файла записаны два числа: количество людей \(N (1≤N≤4000)\) и количество трибун \(K (1≤K≤800)\). Далее записано \(N\) целых чисел \(A_i\) — сумма, которую \(i\)-ый зритель готов потратить \((0≤Ai≤100000)\).
Вывести одно целое число - максимальную прибыль.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи |
| 1 | 40 | \(n,k \le 100\) | тесты |
| 2 | 60 | Без дополнительных ограничений | 1 |
9 4 9 1 5 5 5 5 4 8 80
120