Перед вами в ряд выстроены \(n\) бочек, пронумерованные слева направо, начиная с единицы. В \(i\)-й бочке налито \(a_i\) литров воды.
Вы можете переливать воду из одной бочки в другую. В ходе одного переливания вы можете выбрать две разные бочки с номерами \(x\) и \(y\) (бочка \(x\) должна быть непустой) и перелить любое возможное количество воды из бочки \(x\) в бочку \(y\) (возможно, всю воду). Считайте, что каждая бочка имеет бесконечную емкость, то есть в бочку можно налить сколько угодно воды.
Определите максимальную разность между бочкой с наибольшим количество воды и бочкой с наименьшим количеством воды, если вы можете сделать не более \(k\) переливаний.
Несколько примеров:
- если у вас есть четыре бочки, в каждой из которых по \(5\) литров воды, и \(k = 1\), вы можете вылить \(5\) литров из второй бочки в четвертую, тогда количества литров воды в бочках будут равны \([5, 0, 5, 10]\), и разность между максимальным и минимальным равна \(10\);
- если все бочки — пустые, вы не сможете сделать ни одного переливания, и разность между максимальным и минимальным количеством будет равна \(0\).
Выходные данные
Для каждого набора входных данных, выведите максимальную разность между бочкой с наибольшим количество воды и бочкой с наименьшим количеством воды, если вы можете сделать не более \(k\) переливаний.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 1
5 5 5 5
3 2
0 0 0
|
10
0
|