Kiana and the Dessert Dilemma

Kiana loves desserts. One day, she bought (N) pieces of cake (each with size (A_i)) and decided to share them with Tinytree. Since every cake has a different flavor, they agreed to cut each cake into two parts so that each gets one piece. The process for each cake is as follows:

1. Kiana selects an uncut cake of size (s) and cuts it into two parts. She can choose any nonnegative real numbers (x) and (s-x) as the sizes of the two pieces (one or both parts can even be (0)) as long as (x + (s-x) = s).

2. After seeing the two pieces, if Tinytree still has at least one priority selection right (she has (M) in total), she may choose to use one. Otherwise, she does nothing.

3. If Tinytree uses her priority right, she picks any one of the two pieces and Kiana gets the other. If she does not (or has no rights left), then Kiana picks one of the two pieces and Tinytree gets the other.

Both are extremely smart and aim to maximize the total size of cake they get. Importantly, they know all the cake sizes from the beginning and neither is forced to use all of the priority rights.

Observation and Strategy:

When Tinytree has a priority right available, if Kiana tries an uneven cut, Tinytree will simply pick the larger piece, leaving Kiana with less than (\frac{s}{2}). Therefore, in rounds where Tinytree can act, the best equilibrium for Kiana is to cut the cake equally so that each gets (\frac{s}{2}).

On the other hand, when Tinytree has no priority rights remaining, Kiana can cut the cake arbitrarily unevenly, taking almost the entire cake for herself.

Thus, the optimal strategy for Kiana is to choose the order in which to process the cakes. She should allocate the smallest cakes (minimizing her loss when forced to cut equally) in the rounds where Tinytree has priority rights, and leave the larger cakes for the rounds where Tinytree has none. If we let (m = \min(M, N)) then by sorting the cake sizes in ascending order (B_1 \le B_2 \le \dots \le B_N), Kiana's maximum total cake size is [ \text{Answer} = \sum_{i=m+1}^{N} B_i + \frac{1}{2} \sum_{i=1}^{m} B_i = \left( \sum_{i=1}^{N} B_i \right) - \frac{1}{2} \left( \sum_{i=1}^{m} B_i \right). ]

Your task is to calculate this maximum total size that Kiana can obtain.

inputFormat

The input consists of two lines. The first line contains two integers (N) and (M) where (N) ((1 \le N)) is the number of cakes and (M) ((0 \le M)) is the number of priority rights available to Tinytree. The second line contains (N) space-separated numbers (A_1, A_2, \dots, A_N) representing the sizes of the cakes.

outputFormat

Output a single number, which is the maximum total size of cake that Kiana can obtain. Answers within a reasonable precision error will be accepted.

sample

5 2
1 2 3 4 5

13.5