IOI '04 - Athens, Greece
In a modern city for Greek gods, the streets are geometrically arranged
as a grid with integer coordinates with streets parallel to the and
axes. For each integer value
, there is a horizontal street at
and a vertical street at
. 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 .
To send a message to a cafeteria at
, Hermes only needs
to visit some point on the same horizontal street (with
-coordinate
) or on the same vertical street (with
-coordinate
).
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.
Constraints
Subtask 1 [25 points]
Subtask 2 [25 points]
Subtask 3 [50 points]
Input Specification
The first line contains one integer
: the
number of messages to be sent. The following
lines contain the
coordinates of the
street junctions where the messages are to be
sent. These
lines are in the order in which the messages are to be
sent. Each of these
lines contains two integers
and
: first the
-coordinate and
then the
-coordinate of the street junction.
Output Specification
The output should contain a single line containing one integer: the minimum total distance Hermes needs to travel to send the messages.
Sample Input
5
8 3
7 -7
8 1
-2 1
6 -5
Sample Output
11
Comments
A few additional test cases were added to the first subtask of this problem and all submission rejudged.