Long live the Queen!
After a heavy bombardment by the forces of Queen Alice, the Art Academy has started to collapse. Since, the faithful leader of the Art Academy, was so fanatical in his obsession for art, pieces have been hung everywhere; including on the ceiling. has already managed to remove all his pieces on the walls, so he turns his salvation efforts to the sky, and prepares to catch the pieces as they fall. Fortunately for him, he is not alone. His loyal aide has come back to help him, and together, they will save the art!
The Academy will be represented on a 2D plane where artworks will fall sequentially, given as a point (, ). Either one of them must collect a given piece of art when it falls. Determine the minimum sum of the Manhattan distances that and his aide will have to travel.
For example, if there is a single painting that falls, , his aide starts at , and the painting falls at , the optimal Manhattan distance would be for his aide to move a distance of .starts at
The first line will contain the integer , representing the number of artworks that will fall.
The next line will have the integers , , , and , representing the coordinates of where and his aide will start.
The following lines will have two integers and , representing the coordinate of where the artwork will drop down to.
For all subtasks:
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [70%]
No further constraints.
Save the Academy! Save the artwork! Output the minimum total distanceand his aide will have to travel in order to catch all the artwork.
Sample Input 1
3 1 1 4 4 3 3 1 0 5 2
Sample Output 1