Перед вами в ряд выстроены $$$n$$$ бочек, пронумерованные слева направо, начиная с единицы. В $$$i$$$-й бочке налито $$$a_i$$$ литров воды.
Вы можете переливать воду из одной бочки в другую. В ходе одного переливания вы можете выбрать две разные бочки с номерами $$$x$$$ и $$$y$$$ (бочка $$$x$$$ должна быть непустой) и перелить любое возможное количество воды из бочки $$$x$$$ в бочку $$$y$$$ (возможно, всю воду). Считайте, что каждая бочка имеет бесконечную емкость, то есть в бочку можно налить сколько угодно воды.
Определите максимальную разность между бочкой с наибольшим количество воды и бочкой с наименьшим количеством воды, если вы можете сделать не более $$$k$$$ переливаний.
В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \lt n \le 2 \cdot 10^5$$$) — количество бочек и максимальное количество переливаний, которые вы можете произвести.
Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно изначальному количеству литров воды, которое находится в бочке номер $$$i$$$.
Выведите максимальную разность между бочкой с наибольшим количество воды и бочкой с наименьшим количеством воды, если вы можете сделать не более $$$k$$$ переливаний.
4 1 5 5 5 5
10
3 2 0 0 0
0
В первом примере можно, например, перелить всю воду из второй бочки в четвертую. Тогда количество воды в бочках будет равно $$$[5, 0, 5, 10]$$$, и разность между бочками с максимальным и минимальным количеством воды будет равна $$$10$$$.
Во втором примере ни в одной бочке нет воды, поэтому мы не можем сделать ни одного переливания. Разность между бочками с максимальным и минимальным количеством воды будет равна $$$0$$$.
| Название |
|---|


