У Пети есть массив \(a_i\) из \(n\) целых чисел. Его брату Васе стало завидно, и он решил сделать свой массив из \(n\) чисел.
Для этого он нашел \(m\) целых чисел \(b_i\) (\(m\ge n\)), теперь он хочет выбрать из них какие-то \(n\) чисел, и расставить их в некотором порядке так, чтобы получился массив \(c_i\) длины \(n\).
Чтобы не быть похожим на брата, Вася хочет сделать так, чтобы его массив максимально отличался от массива Пети. А именно, он хочет, чтобы суммарная разница \(D = \sum_{i=1}^{n} |a_i - c_i|\) была максимально возможной.
Помогите Васе узнать, какую наибольшую разницу \(D\) он может получить.
Выходные данные
Для каждого набора входных данных выведите одно число — максимальную суммарную разность \(D\), которую можно получить.
Примечание
В первом примере Вася может, например, сделать массив \((1, 5, 7, 2)\). Тогда суммарная разность будет равна \(D = |6-1|+|1-5|+|2-7|+|4-2| = 5+4+5+2 = 16\).
Во втором примере все числа, доступные Васе, равны 1, поэтому он может собрать только массив \((1, 1, 1)\), для которого разность \(D = 0\).
В третьем примере Вася может, например, сделать массив \((5, 4, 3, 2, 1)\). Тогда суммарная разность будет равна \(D = |1-5|+|2-4|+|3-3|+|4-2|+|5-1| = 4+2+0+2+4 = 12\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
4 6
6 1 2 4
3 5 1 7 2 3
3 4
1 1 1
1 1 1 1
5 5
1 2 3 4 5
1 2 3 4 5
2 6
5 8
8 7 5 8 2 10
2 2
4 1
9 6
4 6
8 10 6 4
3 10 6 1 8 9
3 5
6 5 2
1 7 9 7 2
5 5
9 10 6 3 7
5 9 2 3 9
1 6
3
2 7 10 1 1 5
|
16
0
12
11
10
23
15
25
7
|