Задание №5275

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

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

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

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

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

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

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

5

-20 120 140

90 200 20

147 43 44 

150 30 50 

120 60 20

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

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