Cipele

시간 제한1초메모리 제한64 MB

요약

왼쪽 신발과 오른쪽 신발을 최대한 짝지으되 더 짝지을 수 없게 되고, 짝의 신발 크기 차 최댓값을 최소로 구합니다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 그래프, 투 포인터, 그리디
정답자: 아직 제출이 없습니다

문제

여러 프로젝트에 돈을 대부분 써 버린 Nadan은 자신의 소프트웨어 개발자들에게 좋은 신발을 사 주기로 마음먹었다. 다행히도 Nadan은 지하실에서 왼쪽 신발 N개와 오른쪽 신발 M개를 찾았다. 어디서 왔는지 알 수 없어서 신발 크기는 제각각이다.

Nadan은 최대한 많은 신발을 짝지어 달라고 부탁했다. 모든 신발을 짝지은 뒤에는 새 짝을 고를 수 없어야 한다. 각 짝은 왼쪽 신발 하나와 오른쪽 신발 하나로 이루어져야 한다. 짝을 맞출 때는 못생김을 최소화해야 한다. 한 짝짓기의 못생김은 모든 짝에서 두 신발 크기 차이의 절댓값 중 최댓값으로 정의한다.

입력

첫째 줄에 왼쪽 신발의 개수 N과 오른쪽 신발의 개수 M이 순서대로 주어진다. (1 ≤ N, M ≤ 100 000)

둘째 줄에 왼쪽 신발의 크기 Li가 N개 주어진다. (1 ≤ Li ≤ 109)

셋째 줄에 오른쪽 신발의 크기 Ri가 M개 주어진다. (1 ≤ Ri ≤ 109)

출력

가능한 모든 신발 짝짓기 중에서 못생김의 최솟값을 출력한다.

예제3

예제 1
입력
```
2 3
2 3
1 2 3
```
예상 출력
```
0
```
예제 2
입력
```
4 3
2 39 41 45
39 42 46
```
예상 출력
```
1
```
예제 3
입력
```
5 5
7 6 1 2 10
9 11 6 3 12
```
예상 출력
```
4
```