Maximize Meal Quality
Description
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.
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)$.
On the first and only line, output the answer to the problem.
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.
6 3
7 3 9 1 2 7
5 5
1 1 1 1 1
52
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$.