부정행위 감시

최근 일본 정보 올림피아드의 응시자 수가 크게 늘면서 부정행위를 하는 응시자도 함께 늘어 문제가 되고 있다. 일본 정보 올림피아드 시험장은 직사각형이다. 좌표축은 각각 시험장 벽에 평행하게 잡고, 원점은 시험장의 한 모퉁이에 둔다.

일본 정보 올림피아드 위원회는 응시자의 부정행위를 자동으로 감시하는 장치를 $n$개 만들었다. 각 감시 장치는 $x$축 방향 감시 또는 $y$축 방향 감시 중 하나에 쓸 수 있다.

• 감시 장치 $i$를 $x$축 방향 감시에 쓰면, 감시 장치 $i$는 $p_i \le y \le p_i + d_i$ 영역에 있는 응시자를 감시한다.
• 감시 장치 $i$를 $y$축 방향 감시에 쓰면, 감시 장치 $i$는 $p_i \le x \le p_i + d_i$ 영역에 있는 응시자를 감시한다.

단, $d_i$와 $p_i$ 값은 정수이고 감시 장치마다 따로 설정할 수 있지만, $0 \le d_i$이며 $d_i$가 작을수록 더 정밀하게 감시할 수 있다. 사용하지 않는 감시 장치가 있어도 된다.

그림 1: 감시 장치로 응시자를 감시하는 모습

일본 정보 올림피아드 위원회는 주의가 필요한 응시자 명단을 가지고 있고, 그 응시자들을 최대한 정밀하게 감시하려 한다. 따라서 그림 1처럼 각 응시자를 $x$축 방향 감시를 하는 감시 장치 하나 이상과 $y$축 방향 감시를 하는 감시 장치 하나 이상으로 감시해야 한다. 또한 모든 감시 장치의 $d_i$ 최댓값을 $d_{max}$라 할 때, $d_{max}$를 최대한 작게 해야 한다.

선량한 응시자인 당신에게, 감시 장치의 개수 $n$과 주의가 필요한 응시자의 좌표가 주어질 때 $d_{max}$의 최솟값을 출력하는 프로그램 작성을 요청한다. 단, 응시자는 움직이지 않으며 감시 장치가 감시하는 영역의 경계에 응시자가 있으면 그 응시자는 감시되는 것으로 본다. 또, 응시자의 좌표는 모두 다르다.

입력의 첫째 줄에는 두 정수 $n$, $m$ ($2 \le n \le 200,000$, $1 \le m \le 100,000$)이 공백을 사이에 두고 적혀 있다. 이는 만든 감시 장치의 개수가 $n$개, 주의가 필요한 응시자의 수가 $m$명임을 나타낸다.

이어지는 $m$개 줄(둘째 줄부터 $m+1$번째 줄)은 주의가 필요한 응시자의 좌표를 나타낸다. $j+1$번째 줄($1 \le j \le m$)에는 두 정수 $x_j$, $y_j$ ($0 \le x_j, y_j \le 1,000,000,000$)가 공백을 사이에 두고 적혀 있다. 이는 $j$번째 주의가 필요한 응시자의 좌표가 $(x_j, y_j)$임을 나타낸다.

출력은 표준 출력에 한다. $d_{max}$의 최솟값을 나타내는 정수 하나를 출력하라.