Background

The Fujiwara clan were once powerful ministers. Relying on their overwhelming power, they killed their political enemy Prince Nagaya and thus touched the highest authority.

Was it divine punishment? Even though they repaired temples and did good deeds, the four Fujiwara brothers eventually perished under smallpox.

Problem Description

The interlocking karmic retribution can be seen as $n$ small squares on a plane, with side lengths $1,2,3,\cdots,n$, respectively. Initially, the square with a smaller index is completely contained in the square with a larger index:

To make it easier to record the position of a square, we take the coordinates $(x_i,y_i)$ of the top-left corner as the square's coordinates. In this way, the square is uniquely determined.

Now you need to move the smallest square to $(x_{\rm end},y_{\rm end})$. The moving process must satisfy:

• Each time, you can move at most one square. You may move it by one unit length in one of the four directions: up, down, left, or right.
• During the process, you must ensure that smaller squares are contained within larger squares.

Please find the minimum number of moves.

Input Format

The first line contains three integers $n, x_{\mathrm{end}}, y_{\mathrm{end}}$, with meanings as described above.

The next $n$ lines each contain two integers $x_i, y_i$, describing the coordinates of the top-left corner of the $i$-th smallest square.

Output Format

Output one line with one integer, representing the minimum number of operation steps.

3 2 1
1 0
1 0
0 1

3

15 8 4
9 0
9 1
9 1
8 1
8 2
8 3
7 3
6 3
5 3
4 3
3 3
2 4
2 5
1 6
0 7

24

Hint

Sample 1 Explanation

Constraints and Notes

For all testdata, $1\le n\le 10^5$, $0\le x_i, y_i, x_{\mathrm{end}}, y_{\mathrm{end}}\le 10^9$.

Translated by ChatGPT 5