CCEX Suceava 2023 - clasa a VIII-a | Steaguri

De ziua orașului Suceava, primarul a decis să decoreze strada principală cu steaguri. Acesta a cumpărat $N$ steaguri roșii și $M$ steaguri albastre. Pentru fiecare steag știm înălțimea lui. Mai știm că acesta vrea ca steagurile de aceeași culoare să fie pe aceeași parte a străzii. În plus, acesta vrea să împerecheze câte un steag roșu cu un steag albastru, numărul de perechi fiind cât mai mare posibil. Definim discordanța unei împerecheri ca fiind diferența maximă în modul a înălțimilor steagurilor împerecheate. Primarul vă cere să găsiți discordanța minimă pentru a face orașul Suceava cât mai frumos.

Cerinţă

Se dau două numere întregi $N$ și $M$, apoi $N$ numere (reprezentând înălțimile steagurilor roșii), apoi $M$ numere (reprezentând înălțimile steagurilor albastre). Afișați care este discordanța minimă.

Date de intrare

Fișierul de intrare steaguri.in conține pe prima linie două numere întregi $N$ și $M$ separate printr-un spațiu. Pe a doua linie se vor afla $N$ numere naturale separate printr-un spațiu. Pe a treia linie se vor afla $M$ numere naturale separate printr-un spațiu.

Date de ieşire

În fișierul de ieșire steaguri.out se va scrie pe prima linie rezultatul cerut.

Restricţii și precizări

• $1 \leq n, m \leq 10^5$
• $1 \leq$ înălțimea unui steag $\leq 10^9$
• Pentru teste în valoare de $20$ de puncte, $N = M$.
• Pentru teste în valoare de $50$ de puncte, $1 \leq N,M \leq 5\ 000$.
• Pentru teste în valoare de $40$ de puncte, răspunsul este maxim $150$.

Exemplul 1

steaguri.in

2 3
9 10
4 9 10

steaguri.out

0

Explicație

Am luat perechile $(9, 9)$ și $(10, 10)$.

Exemplul 2

steaguri.in

7 6
7 8 12 21 5 1 2
9 14 3 6 4 11

steaguri.in

3