407438: GYM102791 D Barrels

You have $$$n$$$ barrels lined up in a row, numbered from left to right from one. Initially, the $$$i$$$-th barrel contains $$$a_i$$$ liters of water.

You can pour water from one barrel to another. In one act of pouring, you can choose two different barrels $$$x$$$ and $$$y$$$ (the $$$x$$$-th barrel shouldn't be empty) and pour any possible amount of water from barrel $$$x$$$ to barrel $$$y$$$ (possibly, all water). You may assume that barrels have infinite capacity, so you can pour any amount of water in each of them.

Calculate the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most $$$k$$$ times.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$) — the number of barrels and the number of pourings you can make.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), where $$$a_i$$$ is the initial amount of water the $$$i$$$-th barrel has.

Print the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most $$$k$$$ times.

4 1
5 5 5 5

10

3 2
0 0 0

0

In the first example, you can pour all water from the second barrel to the fourth one. Then amount of water in each barrel will be equal to $$$[5, 0, 5, 10]$$$, and difference between the maximum and the minimum will be equal to $$$10$$$.

In the second example, all barrels are empty, so we can't have anything to pour. The difference between the maximum and the minimum will be equal to $$$0$$$.