Перестановка двох масивів#12967

Перестановка двох масивів

2 секунди
512 мегабайтів
Середня

Вам задано дві послідовності: довжини та довжини .

Нехай k = \min(n, m).

Вам потрібно вибрати перестановку послідовності та перестановку послідовності , щоб максимізувати таку величину:

\sum_{i=1}^k |c_i - d_i|.

Вхідні дані

У першому рядку задано два цілі числа та — довжини послідовностей та відповідно.

У другому рядку задано цілих чисел a_i.

У третьому рядку задано цілих чисел b_i.

1 \le n, m \le 10^5,

0 \le a_i, b_i \le 10^9.

Вихідні дані

В одному рядку виведіть ціле число — максимально можливе значення шуканої величини.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі маємо a = (4, 7, 7, 4), b = (44, 47, 4, 7). Якщо вибрати c = (7, 4, 4, 7) та d = (7, 47, 44, 4), то значення шуканої величини дорівнюватиме |c_1 - d_1| + |c_2 - d_2| + |c_3 - d_3| + |c_4 - d_4| = |7 - 7| + |4 - 47| + |4 - 44| + |7 - 4| = 0 + 43 + 40 + 3 = 86. Це є максимально можливе значення.