Computer Network
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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$$$.