30451번 - Safari 다국어

문제

Safari is a journey that involves going into nature to watch wild animals. Typically, safari participants travel through vast grasslands in four-wheel-drive cars, shortly 4WD cars. Imagine you are on safari in a 4WD car $C$.

Animals appear in specific places on the grassland, where you can consider the places as the points on the plane. There are $n$ animals, indicated as 1ドル$ to $n,ドル in which the animal $i$ appears at the point $p_i$ in the plane. Each animal appears only in its own certain time interval. Specifically, the animal $i$ appears in the time interval $[a_i, b_i]$. So, when the car $C$ stays at $p_i$ for the duration $[v, w],ドル you have the opportunity to observe the animal $i$ for the time period $[v, w] \cap [a_i , b_i]$. Note that if you observe an animal during $[\alpha, \beta],ドル the length of time when you observe it is $|\beta − \alpha|$.

The car $C$ departs from the starting point $s = (0, 0)$ at time 0ドル$ and it moves at speed 1ドル$. Thus time $d$ has passed when $C$ moves distance $d$. The distance is measured in the $L^1$-metric. That is, the distance $d(p_1, p_2)$ between points $p_1 = (x_1, y_1)$ and $p_2 = (x_2, y_2)$ is $|x_1 - x_2 | + |y_1 - y_2|$. It always takes as long as the distance $d(p_1, p_2)$ while the car moves from $p_1$ to $p_2$. Also, the car may stay at a point as long as you need, if necessary. When your safari tour ends at the last sighting point of an animal, you want to know the longest possible time for which you observe the animals.

For example, the figure below shows six animals, indicated as 1ドル$ to 6ドル,ドル which appear at the coordinates $(1, 2),ドル $(2, 1),ドル $(2, 4),ドル $(4, 1),ドル $(5, 3),ドル $(5, 5),ドル respectively, of points in the plane. Let us also indicate as 1ドル$ to 6ドル$ the points of animals. The time intervals when the animals appear are also displayed. First, consider the case the car $C$ is driving along the blue path. The car departs from $s$ at time 0ドル$ and arrives at the point 2ドル$ at time 3ドル$. Departing from it immediately at time 3ドル,ドル the length of time when you observe the animal 2ドル$ is 0ドル$. Afterward, you arrive at the point 3ドル$ at time 6ドル$ and stay there during $[6, 8]$. Next, you arrive at the point 6ドル$ at time 12ドル$ and observe the animal 6ドル$ during $[12, 16]$. Then the total length of time when you observe the animals is 0ドル + 2 + 4 = 6$. Secondly, consider the case the car $C$ is driving along the red path. At first, you arrive at the point 1ドル$ at time 3ドル$ and stay during $[3, 6]$. Departing from it at time 6ドル,ドル you arrive at the point 4ドル$ at time 10ドル$ and stay during $[10, 12]$. Then you arrive at the point 5ドル$ at time 15ドル$ and observe the animal 5ドル$ during $[15, 18]$. In this case, the total length of time when you observe the animals is 2ドル + 2 + 3 = 7,ドル which is longer than the blue path and actually, the length of the longest time when you can observe the animals.

Given $n$ coordinates of points and $n$ time intervals for the appearances of animals, write a program to output the length of the longest possible time when you observe the animals.

입력

Your program is to read from standard input. The input starts with a line containing one integer $n$ (1ドル ≤ n ≤ 5,000円$), where $n$ is the number of animals. The animals are numbered from 1ドル$ to $n$. In the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ that represent the coordinate $(x_i , y_i)$ of the point $p_i$ in the plane where the animal $i$ appears (0ドル ≤ x_i , y_i ≤ 10^6$). Note that the car $C$ is located at $(0, 0)$ at time 0ドル$. The given points containing $(0, 0)$ are all distinct. In the following $n$ lines, the $i$-th line contains two integers $v_i$ and $w_i$ that represent the duration $[v_i , w_i]$ when the animal $i$ appears at $p_i$ (0ドル ≤ v_i < w_i ≤ 10^9$).

출력

Your program is to write to standard output. Print exactly one line. The line should contain the length of the longest time when you can observe the animals.

제한

힌트