ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. The House of Doctor Dee

Time limit: 0.5 second
Memory limit: 64 MB
Mr. X is very fond of the novel “The House of Doctor Dee”, which is set in London in the 16th century and in the end of the 20th century. Rereading the novel once again, Mr. X decided to draw a map of London with routes of the protagonists Dr. Dee and Matthew Palmer. Dr.Dee, who lived in the 16th century, often traveled from his house to St. Paul's Cathedral, and Matthew, who lived in the 20th century, regularly walked from the National Gallery to the British Museum.
Every time it turned out that the protagonists were at the same point in London, Dr. Dee had visions about what was happening to Matthew at that moment. Such moments were often enough, and Mr. X decided to draw the motion trajectories of Dr. Dee and Matthew in such a way that their common part be as long as possible. However, Mr. X is not very good at the topography of London. He assumes that the city is built by a rectangular scheme—each street stretches through the whole city either from west to east or from north to south. The house of Dr. Dee, St. Paul's Cathedral, the National Gallery, and the British Museum are located exactly at the intersections of two orthogonal streets. Moreover, Mr. X is sure that Dr. Dee and Matthew always took one of the shortest possible routes.
Though London is very big, Mr. X has already drawn its map. He has also marked Dr. Dee's house, St. Paul's Cathedral, the National Gallery, and the British Museum on the map. It now remains to draw the required routes.

Input

The first line contains coordinates of Dr. Dee's house separated with a space. The following lines contain the coordinates of St. Paul's Cathedral, the National Gallery, and the British Museum in the same format. All the coordinates are integers with absolute values not exceeding 109.

Output

Output the maximum length of the path that Dr. Dee and Matthew Palmer's routes can have in common.

Sample

inputoutput
2 2
4 4
5 5
3 3
2
Problem Author: Alex Samsonov
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010
To submit the solution for this problem go to the Problem set: 1767. The House of Doctor Dee