Задание №5274

Дети играют в следующую игру. На бесконечном разлинованном на клетки листе введена декартова система координат, при этом клетки таковы, что их вершины находятся во всех точках плоскости, для которых обе координаты целочисленные. Есть некоторое количество бумажных квадратов, стороны которых имеют целочисленные длины. Дети помещают на плоскость эти квадраты (возможно, не все) так, что нижний левый угол каждого квадрата находится на биссектрисе координатного угла, идущей из третьей четверти в первую, и стороны квадратов параллельны осям координат. При этом положение каждого квадрата заранее определено.

Входной файл содержит сведения о размерах квадратов и их возможных положениях на плоскости. Для каждого квадрата указана целочисленная абсцисса положения его нижнего левого угла и длина стороны. Если при размещении на плоскости один квадрат накрывает другой, то дети должны оставить только один из них. Если стороны квадратов касаются, то можно оставить на плоскости оба квадрата. Определите максимальное количество квадратов, которое могут разместить на плоскости дети, и какова при этом максимально возможная величина модуля разности абсцисс положений левых нижних

углов двух квадратов, наиболее удалённых от начала координат.

Входные данные.

В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество квадратов. Следующие N строк содержат пары чисел, обозначающих абсциссу положения левого нижнего угла квадрата на плоскости и длину его стороны. Каждое из чисел целое, не превосходящее 10000. Запишите в ответе два числа: максимальное количество квадратов и максимальную величину модуля разности абсцисс положений левых нижних углов двух квадратов, наиболее удалённых от начала координат.

Типовой пример организации данных во входном файле 

5

-20 120

90 20

147 43 

150 30 

120 20

При таких исходных данных можно поместить на плоскость максимум три квадрата, например, квадраты, описанные в файле под номерами 2, 3 и 5. Максимальная величина модуля разности абсцисс положений левых нижних углов двух квадратов, наиболее удалённых от начала координат, составит 30, если на плоскость помещены квадраты 2, 4 и 5.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.