Computer Network
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard 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.

Examples

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