B. Игра в суммирование
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У них есть массив $$$a_1, a_2,\ldots,a_n$$$. Игра состоит из двух шагов:

  • Сначала Алиса удаляет не более $$$k$$$ элементов из массива.
  • Затем Боб умножает не более $$$x$$$ элементов массива на $$$-1$$$.

Алиса хочет максимизировать сумму элементов массива, в то время как Боб хочет её минимизировать. Найдите сумму элементов массива после игры, если оба игрока играют оптимально.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x,k \leq n$$$) — количество элементов в массиве, ограничение на количество элементов массива, которые может удалить Алиса, и ограничение на количество элементов массива, которые Боб может умножить на $$$-1$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — сумму элементов массива после игры, если оба игрока играют оптимально.

Пример
Входные данные
8
1 1 1
1
4 1 1
3 1 2 4
6 6 3
1 4 3 2 5 6
6 6 1
3 7 3 3 32 15
8 5 3
5 5 3 3 3 2 9 9
10 6 4
1 8 2 9 3 3 4 5 3 200
2 2 1
4 3
2 1 2
1 3
Выходные данные
0
2
0
3
-5
-9
0
-1
Примечание

В первом наборе входных данных для Алисы оптимально удалить единственный элемент массива. Тогда сумма элементов массива будет равна $$$0$$$ после окончания игры.

Во втором наборе входных данных для Алисы оптимально не удалять никакие элементы. Тогда Боб умножит $$$4$$$ на $$$-1$$$. Таким образом, итоговая сумма элементов массива будет равна $$$3+1+2-4=2$$$.

В пятом наборе входных данных для Алисы оптимально удалить $$$9, 9$$$. Затем Боб умножит $$$5, 5, 3$$$ на $$$-1$$$. Таким образом, итоговая сумма элементов массива будет равна $$$-5-5-3+3+3+2=-5$$$.