Programming Tutors

Time limit2sMemory limit512 MB

Summary

Given N students and N tutors in a Manhattan-metric city, find the smallest K such that every student can be matched with a distinct tutor at distance at most K.

Level: Medium6 of 10
Topics: Binary search, Graph, String matching, Union-find
Solved: No attempts yet

Problem

You founded the Bruce Arden Programming Collective, a tutoring program that pairs experienced programmers with beginners. You have $N$ students and $N$ tutors, and now you have to match them one to one. A student travels from their own house to their tutor's house, so you decide to base the matching on travel distance.

Minimising the total distance is not fair. One student might have to travel a huge distance while every other student gets a tutor very close by, even though a different split would give everyone a tutor that is at least somewhat close.

So you minimise the distance travelled by the student who is worst off. One pairing is better than another if the student who travels farthest in the first pairing travels less far than the student who travels farthest in the second pairing.

The students live in a city, so the distance a student travels is not the straight line distance. In this city the distance between the points $(X, Y)$ and $(X', Y')$ is $|X - X'| + |Y - Y'|$ .

Input

The first line contains an integer $N$ , the number of students and also the number of tutors. ( $1 \le N \le 100$ )

Each of the next $N$ lines contains two space separated integers, the location of one student.

Each of the following $N$ lines contains two space separated integers, the location of one tutor.

Every coordinate has absolute value at most $10^8$ . Two students may share a location, two tutors may share a location, and a student and a tutor may share a location.

Output

Print one line with the smallest integer $K$ such that some one to one pairing of students with tutors leaves no pair at distance greater than $K$ .

Examples4

Example 1
Input
```
2
0 0
0 3
0 2
0 5
```
Expected output
```
2
```
Example 2
Input
```
4
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
```
Expected output
```
2
```
Example 3
Input
```
3
0 5
5 2
4 5
3 3
5 2
5 2
```
Expected output
```
5
```
Example 4
Input
```
2
0 0
0 5
-1 4
8 3
```
Expected output
```
10
```