cho.sh

Cakey McCakeFace

정렬된 입구와 출구 타임스탬프가 주어질 때, t + d가 출구 시간인 입구 시간 t의 개수를 최대로 만드는 가장 작은 음이 아닌 시간 차 d를 구한다.

보통5해시맵배열완전 탐색구현면접 대비아직 제출이 없습니다시간 제한7초메모리 제한512 MB

문제

Cakey McCakeFace의 대표 제품인 '알 수 없는 케이크'는 파리 공장에서 매일 구워진다. 이 케이크의 성패는 굽는 시간 하나에 달려 있고, 그 시간은 철저히 비밀이다. 유명한 첩보원 이브가 이 비밀을 빼내려 한다. 이브를 도와라.

케이크는 앞문과 뒷문이 각각 하나씩 있는 거대한 오븐 한 대에서 구워진다. 굽지 않은 케이크는 앞문으로 들어간다. 비밀인 굽는 시간이 정확히 지나면 케이크는 뒷문으로 나온다. 앞문이든 뒷문이든 한 순간에 케이크 한 개만 지나갈 수 있다.

이브는 오븐 앞쪽과 뒤쪽에 감지기를 몰래 설치했다. 감지기는 케이크가 문을 지날 때마다 신호를 기록한다. 시각 tt에 앞문을 지난 케이크는 입구 감지기를 반응시키고, 정확히 cooking_time만큼 지난 뒤 뒷문을 지나면서 출구 감지기를 반응시킨다. 이 공장의 케이크는 언제나 완벽하게 구워진다.

며칠 뒤 이브는 입구 감지기와 출구 감지기가 기록한 시각 목록을 하나씩 받았다. 단위는 밀리초다. 그런데 감지기가 고장 나 있다. 케이크가 지나가지 않았는데 신호를 남기기도 하고, 케이크가 지나갔는데 신호를 남기지 않기도 한다. 이브는 입구 시각과 출구 시각의 대응 개수를 최대로 만드는 시간 차를 찾으면 비밀 굽는 시간을 꽤 잘 추측할 수 있다고 판단했다. 그 값을 구하라.

시간 차 dd의 대응 개수는 기록된 입구 시각 tt 중에서 t+dt + d 역시 출구 시각으로 기록된 것의 개수다.

입력

  • 첫째 줄에 입구 감지기가 반응한 횟수 NN이 주어진다.
  • 둘째 줄에 출구 감지기가 반응한 횟수 MM이 주어진다.
  • 셋째 줄에 입구 감지기가 반응한 시각 NN개가 오름차순으로, 중복 없이, 공백으로 구분되어 주어진다.
  • 넷째 줄에 출구 감지기가 반응한 시각 MM개가 오름차순으로, 중복 없이, 공백으로 구분되어 주어진다.

제한

  • 1≤N,M≤20001 \le N, M \le 2000
  • 각 시각은 0≤t≤1090 \le t \le 10^9인 정수

출력

비밀 굽는 시간의 추측값을 정수 하나로 출력한다. 즉 대응 개수를 최대로 만드는 00 이상의 시간 차를 출력한다. 최댓값을 만드는 시간 차가 여럿이면 그중 가장 작은 값을 출력한다. 어떤 시간 차로도 대응하는 쌍이 하나도 없으면 0을 출력한다.