Задача №115155. Лёша и чтение условий
Мальчик Лёша очень любит задачи по информатике. Но не решать их, а читать условия. И вот, прочитав очередное условие на две с половиной страницы, он понял его формальную часть и теперь просит вас решить саму задачу:
Даны два массива \(a\) и \(b\) из \(n\) элементов, а также число \(m\). Вам нужно переставить числа во втором массиве так, чтобы минимизировать значение выражения:
\(\)(a_1 - b_1) \bmod m + (a_2 - b_2) \bmod m + \ldots + (a_n - b_n) \bmod m\(\)
\(x \bmod m\) — это наименьшее неотрицательное целое число \(y\), такое что \(y = x + k \cdot m\), где \(k\) — целое число.
Например \((-2) \bmod 3 = 1\), так как \(-2 + 3 = 1\), а \(10 \bmod 4 = 2\), так как \(10 - 4 \cdot 2 = 2\).
Помогите Леше найти минимальное возможное значение такой суммы.
В первой строке входных данных даны два числа \(n, m\) (\(1 \leq n \leq 300\,000\), \(1 \leq m \leq 10^9\)) — размер массивов \(a\) и \(b\), а также число \(m\), описанное в условии.
Во второй строке даны \(n\) чисел \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq m\)) — элементы массива \(a\).
В третьей строке даны \(n\) чисел \(b_1, b_2, \ldots, b_n\) (\(1 \leq b_i \leq m\)) — элементы массива \(b\).
Выведите одно число — минимальное возможное значение описанной суммы, которое можно получить, переставив элементы массива \(b\).
В первом примере при перестановке \(b = \{8, 2, 2, 2 \}\) значение cуммы получается
\((1 - 8) \bmod m + (3 - 2) \bmod m + (3 - 2) \bmod m + (7 - 2) \bmod m = 1 + 1 + 1 + 5 = 8\)
Во втором примере при перестановке \(b = \{6, 3, 9, 1\}\) получим значение суммы
\((8 - 6) \bmod m + (4 - 3) \bmod m + (2 - 9) \bmod m + (1 - 1) \bmod m = 2 + 1 + 3 + 0 = 6\)
4 8 1 3 3 7 2 2 2 8
8
4 10 8 4 2 1 1 3 6 9
6