In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Captain Byteasar compasses the waters of Byteic Sea together with his irreplaceable First Officer Bytec. There are islands in the Byteic Sea, which we numbered from 1 to . Captain's ship has docked at the island number 1. Captain's expedition plan is to sail to the island number .
During the voyage, the ship always moves in one of four directions of the world: north, south, east or west. At any time it is either the Captain or the First Officer standing at the helm. Every time the ship will perform turn, they would change at the helm.
Along its way, the vessel may stop at other islands. After each stop, the Captain can decide whether he takes control of the helm first, or not. In other words, for each route leg, leading from an island to another one, one of the sailors stands at the helm while the ship is travelling north or south, and the other controls it while it is moving east or west. In particular, if a given fragment of the route runs exactly in one of the four directions of the world, the ship is controlled by only one of the sailors.
The captain is now considering how to plan a route of the forthcoming voyage and how to divide labour in such a way to spend as little time at the helm. At the same time the Captain does not care how long the calculated route would be. It is assumed that the vessel is sailing at a constant rate of one unit per hour.
The first line of input contains a single integer () denoting the number of islands in the sea. For simplicity, we introduce a coordinate system onto Byteic Sea with axes parallel to the directions of the world. Every island is represented as a single point. Subsequent lines contain descriptions of the islands: -th line contains two integers , () denoting the coordinates of -th island in the sea. Each island bears different coordinates.
Your program should output a single integer denoting the least number of hours the Captain will have to steer the ship on the route from the island number 1 to the number .
For the input data:
5 2 2 1 1 4 5 7 1 6 7
the correct result is:
Explanation of the example: The Captain may designate a route that is indicated in the figure. During the voyage from island (coordinates: ) to the island (coordinates: ) the Captain controls the ship only for an hour, while the ship is sailing south. During the second leg of the trip the Captain controls the vessel only when it is moving east.
Task author: Jakub Radoszewski.<Submit a solution> [0/1]