P7305 [COCI 2018/2019 #1] Cipele

After spending money on all kinds of projects, Nadan decided to provide software developers with high-quality shoes. Nadan found $N$ left shoes and $M$ right shoes in the basement. Since their sources are unknown, the shoe sizes are not necessarily the same. Nadan wants you to match as many pairs of shoes as possible (that is, after all pairings are done, no more pairs can be formed). Each pair must contain one left shoe and one right shoe. When wearing the shoes, the ugliness should be minimized. The ugliness of a set of pairs is defined as the maximum, over all paired shoes, of the absolute difference between the sizes of the left shoe and the right shoe.

The first line contains positive integers $N, M$, representing the numbers of left shoes and right shoes. The second line contains $N$ integers $L_i$, representing the sizes of the left shoes. The third line contains $M$ integers $R_i$, representing the sizes of the right shoes.

Output the minimum possible ugliness among all possible pairing methods.

#### Explanation of Sample 2 Nadan has $4$ left shoes and $3$ right shoes, so at most $3$ pairs can be formed. One pairing method is: **39-46**, 41-42, 45-39. The first pair has the largest absolute size difference, so the ugliness is $7$. A better pairing method is: 39-39, 41-42, 45-46. The ugliness of this method is $1$, which is the minimum among all pairing methods. #### Constraints For $20\%$ of the testdata, $N = M$. For another $50\%$ of the testdata, $N, M \le 5000$. For $100\%$ of the testdata, $1 \le N, M \le 10^5$, $1 \le L_i, R_i \le 10^9$. #### Notes **The score settings of this problem follow the original COCI problem, with a full score of $90$.** **Translated from _T3 Cipele_ of [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #1](https://hsin.hr/coci/archive/2018_2019/contest1_tasks.pdf).** Translated by ChatGPT 5