Алиса и Боб играют в игру. У них есть массив \(a_1, a_2,\ldots,a_n\). Игра состоит из двух шагов:
- Сначала Алиса удаляет не более \(k\) элементов из массива.
- Затем Боб умножает не более \(x\) элементов массива на \(-1\).
Алиса хочет максимизировать сумму элементов массива, в то время как Боб хочет её минимизировать. Найдите сумму элементов массива после игры, если оба игрока играют оптимально.
Выходные данные
Для каждого набора входных данных выведите одно целое число — сумму элементов массива после игры, если оба игрока играют оптимально.
Примечание
В первом наборе входных данных для Алисы оптимально удалить единственный элемент массива. Тогда сумма элементов массива будет равна \(0\) после окончания игры.
Во втором наборе входных данных для Алисы оптимально не удалять никакие элементы. Тогда Боб умножит \(4\) на \(-1\). Таким образом, итоговая сумма элементов массива будет равна \(3+1+2-4=2\).
В пятом наборе входных данных для Алисы оптимально удалить \(9, 9\). Затем Боб умножит \(5, 5, 3\) на \(-1\). Таким образом, итоговая сумма элементов массива будет равна \(-5-5-3+3+3+2=-5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|