Cupa строит подключенную сеть, используя $$$n$$$ компьютеров и один концентратор.
Компьютеры пронумерованы от $$$1$$$ до $$$n$$$. Каждый компьютер $$$i$$$ имеет исходящий провод, который может передать один бит данных на другой конец за $$$d_i$$$ миллисекунд.
Концентратор имеет $$$k$$$ портов, к которым можно подключить провода компьютера, и каждый компьютер имеет один порт.
Cupa требует, чтобы провод каждого компьютера был подключен к какому-то порту — либо в концентраторе, либо в другом компьютере. Также должна быть возможность отправлять данные в концентратор с каждого компьютера напрямую или через другие компьютеры.
Сетевая задержка $$$t_i$$$ для каждого компьютера $$$i$$$ определяется как время, необходимое для отправки одного бита данных с компьютера $$$i$$$ на концентратор. Будем считать, что промежуточным компьютерам не нужно время, чтобы перенаправить полученные данные на свои исходящие провода.
После построения сети Cupa рассчитает сетевую задержку $$$t_i$$$ для каждого компьютера $$$i$$$. Он хочет, чтобы общая задержка сети для всех компьютеров, т. е. $$$t_1 + t_2 + \ldots + t_n$$$, была как можно меньше.
Помогите Cupa построить сеть таким образом, чтобы свести к минимуму общую задержку в сети.
Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ — количество компьютеров и количество портов в хабе ($$$1 \leq k \leq n \leq 100$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ — список моментов передачи данных по проводу каждого компьютера ($$$1 \leq d_i \leq 100$$$).
Выведите одно целое число — минимальную возможную общую задержку в сети.
3 2 20 30 10
70
5 1 10 10 10 10 10
150
5 2 10 10 10 10 10
90
6 3 5 6 2 3 1 4
27
В первом тестовом примере Cupa должна подключить компьютеры $$$2$$$ и $$$3$$$ к концентратору, а компьютер $$$1$$$ подключить к компьютеру $$$3$$$. В этом случае $$$t_1 = 20 + 10 = 30$$$, $$$t_2 = 30$$$ и $$$t_3 = 10$$$. Ответ: $$$t_1 + t_2 + t_3 = 70$$$.
Во втором тестовом примере компьютеры должны быть соединены в цепочку, ведущую к концентратору, в произвольном порядке. Общая задержка в сети составляет $$$10 + 20 + 30 + 40 + 50 = 150$$$.