Существуют различные теории происхождения кратеров на Луне. Большинство ученых придерживается метеоритной теории, согласно которой кратеры возникли при столкновении небесных тел с Луной. Другая версия — это вулканическое происхождение кратеров.
Специалист по исследованию внеземного разума профессор Окулов (однофамилец того самого Окулова — автора известных учебников по программированию) выдвинул альтернативную гипотезу. Как вы думаете, какую? Правильно, связанную с вмешательством внеземного разума. Теперь профессор увлечен поиском подтверждений своей гипотезы.
В распоряжении профессора имеются данные с лунохода, который движется прямолинейно в одном направлении по поверхности Луны. Кратеры имеют форму кругов с целочисленными радиусами. Луноход фиксирует только те кратеры, центры которых лежат на траектории его движения и отправляет на Землю информацию о расстоянии центров кратеров до начальной точки своего движения и их радиусах.
Согласно теории профессора Окулова, два кратера, созданные внеземным разумом для пока неразгаданных целей, либо полностью вкладываются один в другой, либо не пересекаются вообще. Касание кратеров как внутренним, так и внешним образом допустимо. Однако экспериментальные данные с лунохода не подтверждают эту теорию! Тем не менее профессор Окулов не унывает: он прекрасно понимает, что для создания любой стройной теории необходимо пренебречь некоторыми данными, неверными из-за ошибок измерений (или из-за умелой маскировки внеземного разума, который рано или поздно будет обнаружен профессором Окуловым!). Поэтому Окулов хочет выбрать среди имеющихся описаний кратеров наибольший набор, удовлетворяющий его теории.
В первой строке содержится целое число n (1 ≤ n ≤ 2000) — количество обнаруженных кратеров. Следующие n строк содержат описания кратеров в формате «ci ri», где ci — координата центра кратера на прямой движения лунохода, ri — радиус кратера. Все числа ci и ri — целые положительные, не превосходящие 109. Никакие два кратера не совпадают.
В первой строке выведите количество кратеров в искомом наибольшем наборе. В следующей строке через пробел выведите номера входящих в него кратеров. Кратеры нумеруются числами от 1 до n в порядке задания во входных данных. Номера разрешается выводить в произвольном порядке. Если решений несколько, выведите любое.
4
1 1
2 2
4 1
5 1
3
1 2 4
Название |
---|