CF1921D Very Different Array

Petya has an array $ a_i $ of $ n $ integers. His brother Vasya became envious and decided to make his own array of $ n $ integers. To do this, he found $ m $ integers $ b_i $ ( $ m\ge n $ ), and now he wants to choose some $ n $ integers of them and arrange them in a certain order to obtain an array $ c_i $ of length $ n $ . To avoid being similar to his brother, Vasya wants to make his array as different as possible from Petya's array. Specifically, he wants the total difference $ D = \sum_{i=1}^{n} |a_i - c_i| $ to be as large as possible. Help Vasya find the maximum difference $ D $ he can obtain.

N/A

N/A

In the first example, Vasya can, for example, create the array $ (1, 5, 7, 2) $ . Then the total difference will be $ D = |6-1|+|1-5|+|2-7|+|4-2| = 5+4+5+2 = 16 $ . In the second example, all the integers available to Vasya are equal to 1, so he can only create the array $ (1, 1, 1) $ , for which the difference $ D = 0 $ . In the third example, Vasya can, for example, create the array $ (5, 4, 3, 2, 1) $ . Then the total difference will be $ D = |1-5|+|2-4|+|3-3|+|4-2|+|5-1| = 4+2+0+2+4 = 12 $ .