A. Maximize Meal Quality
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ ingredients, numbered from $$$1$$$ to $$$n$$$. The quality of the $$$i$$$th ingredient is $$$a_i$$$.

A dish consists of some nonempty set of ingredients. If a dish contains ingredients with qualities $$$b_1, b_2, ..., b_k$$$, the quality of the dish is $$$\sum\limits_{i=1}^k b_i + \max\limits_{1\leq i\leq k} b_i$$$.

Among all ways to partition the $$$n$$$ ingredients into $$$k$$$ dishes, what is the maximum possible sum of dish qualities? Each ingredient must belong to exactly one dish, and each dish must contain at least one ingredient.

Input

The first line of input consists of two space-separated integers $$$n$$$ and $$$k$$$ $$$(1 \leq k \leq n \leq 2 \cdot 10^5)$$$.

The second line of input consists of $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \leq a_i \leq 10^3)$$$.

Output

On the first and only line, output the answer to the problem.

Examples
Input
6 3
7 3 9 1 2 7
Output
52
Input
5 5
1 1 1 1 1
Output
10
Note

In the first sample test case, one optimal partition is:

  • Dish $$$1$$$ contains ingredients $$$1$$$ and $$$2$$$ with qualities $$$7$$$ and $$$3$$$. The quality of the dish is $$$7 + 3 + \max(7, 3) = 17$$$.
  • Dish $$$2$$$ contains ingredients $$$3$$$ and $$$5$$$ with qualities $$$9$$$ and $$$2$$$. The quality of the dish is $$$9 + 2 + \max(9, 2) = 20$$$.
  • Dish $$$3$$$ contains ingredients $$$4$$$ and $$$6$$$ with qualities $$$1$$$ and $$$7$$$. The quality of the dish is $$$1 + 7 + \max(1, 7) = 15$$$.

The sum of dish qualities is $$$17 + 20 + 15 = 52$$$. It can be proven that no larger sum is possible.

In the second sample test case, each ingredient must belong to a distinct dish. The sum of qualities is then $$$5 \cdot (1 + 1) = 10$$$.