Monkeys live in trees. Their world can be abstracted as a two-dimensional grid with integer coordinates. The ground is the x-axis and trees are planted perpendicular to the x-axis (in both the positive and negative y directions). Monkeys can only move up and down trees, and horizontally on the ground. Therefore, the distance between two monkeys is calculated as follows:
- If the two monkeys have the same x coordinate (meaning that they're in the same tree), the distance between them is the absolute difference between their y coordinates. See the blue pair in the image below.
- Otherwise, the distance is the distance between monkey1 and the ground + the distance between monkey2 and the ground + the absolute difference between their x coordinates. See the green and purple pairs in the image below.
The government is about to make a bold decision that will make the lives of the monkeys easier. They will minimize the maximum distance between any pair of monkeys by moving the ground to a horizontal line y = N, where N is an integer. If the ground is already at the optimal position, it will not be moved.
You are given two ints x and y, The ith monkey lives at (x[i], y[i]), where the absolute values of x[i] and y[i] are each less than or equal to 109. Return the maximum distance between any pair of monkeys after the the ground is moved to the optimal position. The distance should be returned as a String with no leading zeros.