Tracy the farmer is looking out at her field of cows. She has brown cows and black and white cows on a field of size by . Today, Tracy wants to pick one brown cow and one black and white cow to milk. Her cows are very special - the lesser the distance she has to travel between them, the better the milk they produce will be. As such, she wants to pick two cows such that the distance she has to travel between them is as little as possible.
Tracy also has a very special tractor. Her tractor allows her to magically teleport between either two rows or two columns. She can choose which to teleport between, and she can only use this tractor once.
Given the locations of Tracy's cows, can you output the distance between the two cows she should milk to have the best possible milk?
Input Specification
The first line will contain two integers, and , the number of brown cows and the number of black and white cows Tracy has, respectively.
The next lines will contain two integers each, and , the and position of one brown cow on the field.
The next lines will contain two integers each, and , the and position of one black and white cow on the field.
Output Specification
Output a single integer, the distance between the two cows Tracy should milk to have the best possible milk.
Subtasks
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
Sample Input 1
2 1
4 4
1000 2
1 1
Sample Output 1
1
Explanation for Sample 1
Tracy chooses to move between the second brown cow and first black and white cow. The x-distance between these two cows is and the y-distance between these two cows is . Since she can use her tractor, she uses it to teleport between the two columns. Thus, she only has to travel a distance of between the rows, making this the minimum distance.
Sample Input 2
2 2
1 1
1 2
4 4
5 5
Sample Output 2
2
Comments