Kiana likes desserts. One day, she buys $N$ pieces of cake from a shop to share with Tinytree. The size of the $i$-th piece of cake is denoted by $A_i$.

Since each piece of cake has a different flavor, Kiana and Tinytree decide to cut each piece into two parts, and each person will choose one part to enjoy. However, cutting cake is a difficult task. After discussion, Kiana decides to do the cutting, while Tinytree has $M$ "priority selection rights," which allow her to have priority in choosing a piece after it has been cut. Specifically, the two follow the process below:

Step 1: Kiana chooses a piece of cake that has not yet been cut according to her own strategy and cuts it into two parts. The size of each part can be any non-negative real number, and the sum of the sizes of the two parts is equal to the size of the piece before it was cut.

Step 2: After observing the sizes of the two parts cut by Kiana, if Tinytree still has "priority selection rights" remaining, she can decide whether to consume one "priority selection right" to make a priority choice.

Step 3: If Tinytree chooses to use a "priority selection right," she can choose either of the two parts, and the other part goes to Kiana. If Tinytree chooses not to use it or has already exhausted her $M$ "priority selection rights," then Kiana chooses either of the two parts, and the other part goes to Tinytree. Then, the two return to Step 1 until all pieces of cake have been cut.

Assume that both Kiana and Tinytree are sufficiently intelligent and always try to maximize the total size of the cake they obtain when it is their turn to act. Both are aware of the sizes of the $N$ pieces of cake before starting to cut the first piece. Tinytree is not required to use all of her "priority selection rights." Now, Kiana wants to know the total size of the cake she can obtain. Since Kiana cannot calculate this herself, she hopes you can help her.

Input

The first line contains two positive integers $N$ and $M$ ($1 \le M \le N \le 2500$), representing the total number of cakes and the initial number of "priority selection rights" Tinytree has.

The second line contains $N$ positive integers, where the $i$-th number $A_i$ ($1 \le A_i \le 50000$) represents the size of the $i$-th piece of cake.

Output

Output a single line containing a real number representing the total size of the cake Kiana can ultimately obtain. All outputs should be precise to six decimal places.

Examples

Input 1

4 3
4 3 2 1

Output 1

5.250000

Note 1

In this example, there are 4 pieces of cake with sizes 4, 3, 2, and 1, and Tinytree has three "priority selection rights." The two can distribute the cakes in the following order and manner:

First piece: Kiana chooses the cake of size 3 and cuts it into two parts of size 1.25 and 1.75. Tinytree uses one "priority selection right" to take the 1.75 part. Kiana currently has a total cake size of 1.25.

Second piece: Kiana chooses the cake of size 1 and cuts it into two parts of size 0 and 1. Tinytree does not use a "priority selection right," and Kiana takes this cake entirely. Kiana currently has a total cake size of 2.25.

Third piece: Kiana chooses the cake of size 2 and cuts it into two parts of size 1 and 1. Tinytree uses one "priority selection right" to take the 1 part. Kiana currently has a total cake size of 3.25.

Fourth piece: Kiana chooses the cake of size 4 and cuts it into two parts of size 2 and 2. Tinytree uses one "priority selection right" to take the 2 part. Kiana currently has a total cake size of 5.25.

In summary, the example outputs 5.250000, and it can be proven that in this scenario, if either person changes their strategy, the total size of the cake they obtain cannot be increased.