Hermes#2123
In a modern city inhabited by Greek gods, the streets are laid out as an integer grid, running parallel to the and axes. For every integer , there is a horizontal street at y=Z and a vertical street at x=Z. Each intersection of these streets is located at integer coordinates, and thus each pair of integers defines a unique intersection. On hot days, the gods relax in cafeterias situated at these intersections. Hermes, the messenger, must deliver light messages to the gods in the cafeterias, traveling only along the city's streets. Each message is intended for a specific god, but it is not a problem if other gods see the message.
The messages must be delivered in the specified order, so Hermes is given the cafeteria coordinates in that exact sequence. Hermes begins at the point . To deliver a message to a cafeteria at coordinates (X_i, Y_i), Hermes only needs to visit any point on the same horizontal street (with -coordinate Y_i) or on the same vertical street (with -coordinate X_i). Once all messages are delivered, Hermes stops.
Your task is to write a program that, given the sequence of cafeteria coordinates, finds the minimum total path length Hermes must travel to deliver all the messages.
The first line of the input contains a single integer – the number of messages to be delivered. The following lines contain the coordinates of the street intersections where the messages must be sent, in the specified order. Each of these lines contains two integers: the first is the -coordinate, and the second is the -coordinate of the intersection.
For all tests, 1 \leq N \leq 20000, -1000 \leq X_i, Y_i \leq 1000. In of the tests: 1 \leq N \leq 80.
The output must contain a single integer – the minimum total path length necessary for Hermes to deliver all the messages.
Example 1