Взуття#9010

Взуття

1 секунда

128 мегабайтів

Легка

Витративши більшу частину своїх грошей на різні проекти, Надан вирішив дозволити собі якісне взуття для своїх розробників програмного забезпечення. На щастя для Надана, він знайшов $n$ лівих черевиків і $m$ правих черевиків у своєму підвалі. Оскільки їхнє походження невідоме, черевики були різних розмірів.

Надан попросив Вас з'єднати якнайбільше взуття (нову пару не можна вибрати після з'єднання всіх черевиків). Кожна пара має складатися з одного лівого та одного правого черевика. Підбираючи взуття, Ви повинні переконатися, що потворність зведена до мінімуму. Потворність однієї пари визначається як максимум абсолютної різниці розмірів взуття між усіма парами взуття.

Вхідні дані

Перший рядок містить два натуральні числа $n$ і $m$ ( $1 \leq n, m \leq 1 0^{5}$ 1 ≤ n, m ≤ 10^5) - кількість лівих і правих черевиків.

Другий рядок містить $n$ чисел $l_{i}$ l_i ( $1 \leq l_{i} \leq 1 0^{9}$ 1 ≤ l_i ≤ 10^9) - розміри лівих черевиків.

Третій рядок містить $m$ чисел $r_{i}$ r_i ( $1 \leq r_{i} \leq 1 0^{9}$ 1 ≤ r_i ≤ 10^9) - розміри правих черевиків.

Вихідні дані

Виведіть мінімальну потворність між усіма можливими парами взуття.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

Розглянемо другий тест.

У Надана $4$ лівих і $3$ правих черевиків, максимальна кількість пар, які можна отримати, $3$ . Одна з можливих пар: $39$ - $46$ , $41$ - $42$ , $45$ - $39$ . Потворність дорівнює $7$ через першу пару.

Найкращою парою буде: $39$ - $39$ , $41$ - $42$ , $45$ - $46$ . Потворність дорівнює $1$ , що є мінімально можливим.