시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

## 문제

A known Polish proverb is: 'The apple always falls near the apple tree'1. Your task is to check this proverb experimentally. Positions of apple trees and apples can be identified with points on a plane. The distances between points are defined by Manhattan metric:

d((x1, y1), (x2, y2)) = |x1 - x2| + |y1 - y2|

Let us assume that every apple has fallen from the apple tree closest to it.

Write a program that:

• reads a description of positions of apple trees and apples from the standard input,
• computes the smallest distance between an apple and its apple tree,
• writes the result to the standard output.

1An English equivalent of this proverb is: 'Like father, like son' or 'Like mother, like daughter'.

## 입력

The first line of input contains two integers n and m (1 ≤ n, m ≤ 100 000), separated with a single space and denoting the number of apple trees and the number of apples. The second line of input contains 2 · n integers from the range [0,108], separated with single spaces and denoting the pairs of coordinates of apple trees: x1 y1 x2 y2 ... xn yn. The third line of input contains 2 · m integers from the range [0,108], separated with single spaces and denoting the pairs of coordinates of apples: x'1 y'1 x'2 y'2 ... x'n y'n. We treat both apple trees and apples as points on a plane; there can be multiple apple trees and multiple apples in one point.

## 출력

The first and only line of output should contain the smallest distance between an apple and its apple tree.

## 예제 입력 1

3 4
0 2 2 0 2 2
1 1 2 1 2 3 1 4


## 예제 출력 1

1