A13670. New Game Plus!

Wabbit is playing a game with $n$ bosses numbered from $1$ to $n$ . The bosses can be fought in any order. Each boss needs to be defeated exactly once. There is a parameter called boss bonus which is initially $0$ .

When the $i$ -th boss is defeated, the current boss bonus is added to Wabbit's score, and then the value of the boss bonus increases by the point increment $c_i$ . Note that $c_i$ can be negative, which means that other bosses now give fewer points.

However, Wabbit has found a glitch in the game. At any point in time, he can reset the playthrough and start a New Game Plus playthrough. This will set the current boss bonus to $0$ , while all defeated bosses remain defeated. The current score is also saved and does not reset to zero after this operation. This glitch can be used at most $k$ times. He can reset after defeating any number of bosses (including before or after defeating all of them), and he also can reset the game several times in a row without defeating any boss.

Help Wabbit determine the maximum score he can obtain if he has to defeat all $n$ bosses.

The first line of input contains two spaced integers $n$ and $k$ ( $1 \leq n \leq 5 \cdot 10^5$ , $0 \leq k \leq 5 \cdot 10^5$ ), representing the number of bosses and the number of resets allowed.

The next line of input contains $n$ spaced integers $c_1,c_2,\ldots,c_n$ ( $-10^6 \leq c_i \leq 10^6$ ), the point increments of the $n$ bosses.

Output a single integer, the maximum score Wabbit can obtain by defeating all $n$ bosses (this value may be negative).

In the first test case, no resets are allowed. An optimal sequence of fights would be

- Fight the first boss $(+0)$ . Boss bonus becomes equal to $1$ .
- Fight the second boss $(+1)$ . Boss bonus becomes equal to $2$ .
- Fight the third boss $(+2)$ . Boss bonus becomes equal to $3$ .

Thus the answer for the first test case is $0+1+2=3$ .

In the second test case, it can be shown that one possible optimal sequence of fights is

- Fight the fifth boss $(+0)$ . Boss bonus becomes equal to $5$ .
- Fight the first boss $(+5)$ . Boss bonus becomes equal to $4$ .
- Fight the second boss $(+4)$ . Boss bonus becomes equal to $2$ .
- Fight the third boss $(+2)$ . Boss bonus becomes equal to $-1$ .
- Reset. Boss bonus becomes equal to $0$ .
- Fight the fourth boss $(+0)$ . Boss bonus becomes equal to $-4$ .

Hence the answer for the second test case is $0+5+4+2+0=11$ .