{"scoring":null,"notes":"In the first example test, Cupa should connect computers $2$ and $3$ to the hub, and connect computer $1$ to computer $3$. In this case, $t_1 = 20 + 10 = 30$, $t_2 = 30$, and $t_3 = 10$. The answer is $t_1 + t_2 + t_3 = 70$.\r\n\r\nIn the second example test, the computers should be connected in a chain leading to the hub in arbitrary order. The total network latency is $10 + 20 + 30 + 40 + 50 = 150$.","legend":"Cupa is building a connected network using $n$ computers and a single hub.\r\n\r\nThe computers are numbered from $1$ to $n$. Each computer $i$ has an outgoing wire that can transfer one bit of data to the other end in $d_i$ milliseconds.\r\n\r\nThe hub has $k$ ports into which the computer's wires can be connected, and each computer has a single port.\r\n\r\nCupa requires each computer's wire to be connected to some port~--- either in the hub or in another computer. It should also be possible to send data to the hub from every computer, either directly or via other computers.\r\n\r\nThe network latency $t_i$ for each computer $i$ is defined as the time it takes to send one bit of data from computer $i$ to the hub. We will assume that it takes no time for intermediate computers to redirect received data to their own outgoing wires.\r\n\r\nAfter the network is built, Cupa will calculate the network latency $t_i$ for each computer $i$. He wants the total network latency over all computers, i.e. $t_1 + t_2 + \\ldots + t_n$, to be as small as possible.\r\n\r\nHelp Cupa to build the network in a way that minimizes the total network latency.","authorLogin":"tourist","language":"english","timeLimit":2000,"output":"Print a single integer~--- the minimum possible total network latency.","inputFile":"stdin","outputFile":"stdout","input":"The first line contains two integers $n$ and $k$~--- the number of computers and the number of ports in the hub ($1 \\leq k \\leq n \\leq 100$).\r\n\r\nThe second line contains $n$ integers $d_1, d_2, \\ldots, d_n$~--- the list of data transfer times through each computer's wire ($1 \\leq d_i \\leq 100$).","authorName":"Gennady Korotkevich","sampleTests":[{"output":"70\r\n","input":"3 2\r\n20 30 10\r\n","inputFile":"example.01","outputFile":"example.01.a"},{"output":"150\r\n","input":"5 1\r\n10 10 10 10 10\r\n","inputFile":"example.02","outputFile":"example.02.a"},{"output":"90\r\n","input":"5 2\r\n10 10 10 10 10\r\n","inputFile":"example.03","outputFile":"example.03.a"},{"output":"27\r\n","input":"6 3\r\n5 6 2 3 1 4\r\n","inputFile":"example.04","outputFile":"example.04.a"}],"name":"Computer Network","interaction":null,"memoryLimit":536870912,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Виталий Аксенов \\\\\r\n         Разработка: & Виталий Аксенов \\\\\r\n     \\end{tabular}\r\n}\r\n\r\nПусть у нас есть какая-то конфигурация~--- она выглядит как k путей, которые идут из хаба (центра). Посмотрим на самые удалённые компьютеры на каждом пути от хаба в сети. В суммарных задержках их задержки учитываются один раз. Также, на каждом из $k$ путей задержки предпоследнего компьютера учитываются два раза. И так далее.\r\n\r\nНам выгодно, чтобы в конфигурации было $k$ компьютеров, у которых задержка учитывается один раз, $k$ компьютеров, у которых задержка учитывается два раза, и так далее. Чтобы минимизировать сумму задержек, нам следует отсортировать все задержки по убыванию, и первые $k$ компьютеров использовать с коэффициентом $1$, вторые $k$ компьютеров использовать с коэффициентом $2$, и так далее."}