Скоро у Лизы день рождения! Родители долго думали, чем порадовать свою любимую дочку, и решили, что лучше всего подарить ей путешествие в Нью-Йорк. Ведь это — такой оригинальный подарок! Так как Лиза — уже самостоятельная девочка, она вполне может сама выбрать, где ей поселиться в Нью-Йорке. Однако родители очень беспокоятся за нее, поэтому они разрешили ей выбирать только из H безопасных пятизвездочных отелей.

Лиза — общительная девочка, и у неё очень много друзей. Узнав, что она будет отмечать день рождения в Нью-Йорке, друзья немедленно отправились туда и поселились в C хостелах.

Лиза по случаю дня рождения устраивает маленькую вечеринку. К сожалению, никто из её друзей не хочет пропустить очередную серию нового реалити-шоу «Home-2», но как только серия закончится, все они одновременно выйдут из своих хостелов и поедут поздравлять Лизу. Она — девочка нетерпеливая, поэтому хочет выбрать отель так, чтобы последний друг приехал к ней как можно раньше, т.е. находился как можно ближе. Так как она тоже не хочет отвлекаться от просмотра высокоинтеллектуального шоу, она попросила вас помочь ей с выбором отеля. Конечно, за это она тоже пригласит вас на вечеринку!

Как известно, Нью-Йорк представляет собой идеальную прямоугольную сетку улиц: с севера на юг тянутся N авеню, а с запада на восток — M улиц. Наличием Бродвея мы в этой задаче пренебрежем. Можно считать, что каждый объект находится в узле этой сетки (и, таким образом, однозначно задается номером авеню и номером улицы, возле пересечения которых он расположен), а два соседних узла сетки находятся на расстоянии одного километра.