Инна, Дима и Сережа собрались в комнате. На улице холодно, поэтому Сережа предложил ребятам поиграть в настольную игру «Пупсики».
Поле для игры в «Пупсики» представляет собой безграничную плоскость, на которой находятся n синих пупсиков и m красных. Каждый пупсик — это отрезок, который растет во времени. В момент времени t синий пупсик (x, y) представляет собой синий отрезок с концами в точках (x - t, y + t), (x + t, y - t). Аналогично, в момент времени t красный пупсик (x, y) представляет собой красный отрезок с концами в точках (x + t, y + t), (x - t, y - t) плоскости. Первоначально, в момент времени t = 0, все пупсики — это точки на плоскости.
Цель игры — найти первый целочисленный момент времени, в который на плоскости будет существовать прямоугольник ненулевой площади, стороны которого целиком покрываются некоторыми пупсикам (сторона может быть покрыта несколькими пупсиками). Более формально, для любой точки границы прямоугольника должен существовать пупсик, которому эта точка принадлежит. При этом нужно считать, что пупсики являются замкнутыми отрезками, то есть содержат свои конечные точки.
Вам заданы позиции все пупсиков — помогите ребятам найти требуемый момент времени.