Алиса и Боб играют в игру. У них есть множество, который изначально состоит из \(n\) целых чисел. Игра длится \(k\) ходов. Во время каждого хода происходит следующее:
- сначала Алиса выбирает целое число из множества. Она может выбрать любое целое число кроме максимального. Пусть целое число, выбранное Алисой, равно \(a\);
- затем Боб выбирает целое число из множества. Он может выбрать любое целое число которое больше \(a\). Пусть целое число, выбранное Бобом, равно \(b\);
- наконец, и \(a\), и \(b\) удаляются из множества, а значение \(b - a\) добавляется к счету игры.
Изначально счет игры равен \(0\). Алиса хочет максимизировать итоговый счет, а Боб хочет минимизировать его. Предположив, что и Алиса, и Боб играют оптимально, вычислите итоговый счет игры.
Выходные данные
Выведите одно целое число — итоговый счет игры (при условии, что и Алиса, и Боб играют оптимально).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
3 4 1 5 2
|
4
|
|
2
|
7 3
101 108 200 1 201 109 100
|
283
|