Sakura Beauty

Sakura \(\zeta\) loves to admire cherry blossoms. There are \(n\) cherry blossoms, and during the falling process, the beauty of the \(i\)-th fallen blossom is \(a_i\). After each blossom falls, the total aesthetic enjoyment is increased by the maximum beauty among the fallen blossoms so far, i.e. \(\max_{1 \le j \le i}{a_j}\).

You are allowed to perform exactly \(k\) swaps, where in each swap you exchange the positions of two distinct blossoms in the falling order (swapping an element with itself is not allowed, but you may swap the same pair multiple times). Your task is to maximize the total aesthetic enjoyment defined as

[ S = \sum_{i=1}^{n} \max_{1 \le j \le i}{a_j}. ]

Help Sakura \(\zeta\) by outputting the maximum possible value of \(S\) after exactly \(k\) swaps.

Note: Even if you achieve the optimal order with fewer than \(k\) effective swaps, you must still perform exactly \(k\) swaps (redundant swaps that do not change the order are allowed).

inputFormat

The first line contains two integers \(n\) and \(k\) (the number of cherry blossoms and the number of swaps).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\), where \(a_i\) represents the beauty of the \(i\)-th fallen blossom.

outputFormat

Output a single integer, which is the maximum total aesthetic enjoyment \(S = \sum_{i=1}^{n} \max_{1 \le j \le i}{a_j}\) that can be achieved after exactly \(k\) swaps.

sample

3 1
3 1 2

9