410260: GYM103994 B Лёша и чтение условий

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Лёша и чтение условийограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Мальчик Лёша очень любит задачи по информатике. Но не решать их, а читать условия. И вот, прочитав очередное условие на две с половиной страницы, он понял его формальную часть и теперь просит вас решить саму задачу:

Даны два массива $$$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$$$.

ПримерыВходные данные
4 8
1 3 3 7
2 2 2 8
Выходные данные
8
Входные данные
4 10
8 4 2 1
1 3 6 9
Выходные данные
6
Примечание

В первом примере при перестановке $$$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$$$

加入题单

上一题 下一题 算法标签: