410357: GYM104012 C Computer Network

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Computer Networktime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Cupa is building a connected network using $$$n$$$ computers and a single hub.

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

The hub has $$$k$$$ ports into which the computer's wires can be connected, and each computer has a single port.

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

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

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

Help Cupa to build the network in a way that minimizes the total network latency.

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

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

Output

Print a single integer — the minimum possible total network latency.

ExamplesInput
3 2
20 30 10
Output
70
Input
5 1
10 10 10 10 10
Output
150
Input
5 2
10 10 10 10 10
Output
90
Input
6 3
5 6 2 3 1 4
Output
27
Note

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

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

加入题单

上一题 下一题 算法标签: