Version
Version 1.2
Athens
Greece

hermes
hermes

Hermes

PROBLEM

In a modern city for Greek gods, the streets are geometrically arranged as a grid with
integer coordinates with streets parallel to the x and y axes. For each integer value Z, there
is a horizontal street at y=Z and a vertical street at x=Z. This way, integer coordinate pairs
represent the street junctions. During the hot days, the gods rest in cafeterias at street
junctions. Messenger Hermes is to send photon messages to gods resting in the cafeterias
by only moving along the city streets. Each message is for a single god, and it does not
matter if the other gods see the message.

The messages are to be sent in a given order, and Hermes is provided the coordinates of the
cafeterias in that order. Hermes starts from (0,0). To send a message to a cafeteria at (Xi,Yi),
Hermes only needs to visit some point on the same horizontal street (with y-coordinate Yi)
or on the same vertical street (with x-coordinate Xi). Having sent all of the messages,
Hermes stops.

You are to write a program that, given a sequence of cafeterias, finds the minimum total
distance Hermes needs to travel to send the messages.

Note (RiseOJ) — The original statement describes file-based input/output; on this judge your program must read from standard input and write to standard output instead.

In all inputs, 1≤N≤20000, -1000≤Xi,Yi ≤1000. Additionally, in 50% of the inputs, 1≤N≤80.
5
8 3
7 -7
8 1
-2 1
6 -5
11

The input file name is hermes.in. The first line contains one integer N: the number of
messages to be sent. The following N lines contain the coordinates of the N street junctions
where the messages are to be sent. These N lines are in the order in which the messages are
to be sent. Each of these N lines contains two integers: first the x-coordinate and then the
y-coordinate of the street junction.

The output file name is hermes.out. The file is to contain a single line containing one
integer: the minimum total distance Hermes needs to travel to send the messages.

EXAMPLE INPUT AND OUTPUT

hermes.in

hermes.out

생성자가 기록되지 않았습니다.

출처 IOI 2004