Мистер Икс очень любит роман «Дом доктора Ди», действие которого происходит в Лондоне в XVI и в конце XX века. В очередной раз перечитывая этот роман, Мистер Икс решил нарисовать карту Лондона с маршрутами движения главных героев книги — доктора Ди и Мэтью Палмера. Доктор Ди, живший в XVI веке, часто совершал путешествие от своего дома до Собора Святого Павла, а Мэтью, живший в XX веке, регулярно проделывал путь от Национальной галереи до Британского музея.

Каждый раз, когда герои романа оказывались в одной точке Лондона, у доктора Ди возникали видения, рассказывающие ему о том, что происходит в этот момент с Мэтью. Такие моменты случались довольно часто, поэтому Мистер Икс решил изобразить на карте Лондона траектории движения героев так, чтобы длина общей части этих траекторий была как можно больше. Но Мистер Икс не силён в топографии Лондона. Он считает, что город выстроен по прямоугольному плану — все улицы идут либо с запада на восток, либо с севера на юг, проходя через весь город от края до края. Дом доктора Ди, Собор Святого Павла, Национальная галерея и Британский музей располагаются в точности на пересечении двух перпендикулярных улиц. Кроме того, Мистер Икс уверен, что герои романа всегда перемещались по одному из кратчайших доступных им путей.

Несмотря на то, что Лондон поистине огромен, Мистер Икс уже нарисовал карту города. Затем он отметил на ней дом доктора Ди, Собор Святого Павла, Национальную галерею и Британский музей. Осталось лишь изобразить нужные маршруты.

В первой строке через пробел записаны координаты дома доктора Ди. В следующих строках аналогичным образом заданы координаты Собора Святого Павла, Национальной галереи и Британского музея. Все координаты — целые числа, не превосходящие по модулю 10⁹.

Выведите максимальную длину общей части траекторий движения доктора Ди и Мэтью Палмера.