대포

넥슨에서 새로 개발하고 있는 전략 시뮬레이션 게임은 다음과 같은 규칙으로 이루어져 있다.

1. 전투가 벌어지는 곳은 가로 $N$개, 세로 $N$개의 칸이 있는 $N \times N$ 격자 모양이다. 가장 왼쪽 아래 칸은 $(1, 1)$이고, 가장 오른쪽 위 칸은 $(N, N)$이다.
2. 각 격자의 눈에는 우리편 $k$대, 적 $k$대의 대포가 놓여 있을 수 있다.
3. 대포는 움직일 수 없다.
4. 대포의 사정 거리, 즉 포탄이 가장 멀리 갈 수 있는 거리는 다음과 같이 정해진다. 현재 우리 편 대포의 위치가 $(a, b)$이고, 적 대포의 위치가 $(a^\prime, b^\prime)$이라면, 포탄이 간 거리는 $|a - a^\prime| + |b - b^\prime|$이다.
5. 모든 대포의 사정 거리는 같다.
6. 우리 편부터 시작하여 한 턴에 하나의 대포를 발사할 수 있으며, 포탄을 맞은 대포는 파괴된다.

규칙이 위와 같이 주어졌을 때, 당신은 당연히 게임에서 이기고 싶다. 그러려면 상대가 나의 어느 대포를 먼저 파괴할 지 알 수 없기 때문에, 내가 가지고 있는 어떤 대포도 모든 상대 대포를 파괴할 수 있도록 하고 싶다. 대포의 사정거리를 업그레이드하려면 그 비용이 거리에 따라 늘어나기 때문에, 가장 적은 비용을 들이고 싶다. 아래 그림의 예를 고려해보자. 우리 편의 대포는 A, 적의 대포는 B로 표현하였다.

$(1, 2)$, $(2, 3)$, $(3, 1)$ 위치에 우리 편의 대포가 셋 있고, $(3, 5)$, $(4, 5)$, $(5, 4)$ 위치에 적의 대포가 셋이 있다.

• $(1, 2)$에 있는 우리 편 대포가 가장 멀리 떨어진 $(5, 4)$에 있는 적의 대포를 파괴하려면 사정 거리가 $6$이어야 한다. ($|1-5| + |2-4| = 6$)
• $(2, 3)$에 있는 우리 편 대포가 가장 멀리 떨어진 $(5, 4)$에 있는 적의 대포를 파괴하려면 사정 거리가 $4$여야 한다. ($|2-5| + |3-4| = 4$)
• $(3, 1)$에 있는 우리 편 대포가 가장 멀리 떨어진 $(5, 4)$에 있는 적의 대포를 파괴하려면 사정 거리가 $5$여야 한다. ($|3-5| + |1-4| = 5$)

위 세 가지 경우를 모두 고려하면, 대포의 사정 거리가 최소 $6$이어야 적의 모든 대포를 공격할 수 있는 것을 알 수 있다.

격자의 크기, 대포의 수, 대포의 위치가 주어졌을 때 적의 모든 대포를 공격할 수 있는 최소 사정 거리를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 격자의 크기를 나타내는 자연수 $N$ ($1$ 이상 $1\,000\,000\,000$ 이하)과 각 편의 대포의 수 $k$ ($1$ 이상 $1\,000\,000$ 이하)가 주어진다.

다음 $k$줄에는 두 정수 $a$ $b$가 주어지는데, 각각 우리 편 대포의 좌표 $(a, b)$를 나타낸다. $a$, $b$는 모두 $1$ 이상 $N$ 이하이다.

다음 $k$줄에도 두 정수 $a^\prime$ $b^\prime$가 주어지는데, 각각 적 대포의 좌표 $(a^\prime, b^\prime)$를 나타낸다. $a^\prime$, $b^\prime$는 모두 $1$ 이상 $N$ 이하이다.

출력 형식

한 줄로 결과를 출력한다. 여기에는 적 대포를 모두 공격할 수 있는 최소 사정 거리를 나타내는 정수 하나를 출력한다.

예제

5 3
1 2
2 3
3 1
3 5
4 5
5 4

6

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설