(Е. Джобс) В лесополосе высаживают плодовые деревья рядами на одинаковом расстоянии друг от друга. Между соседними саженцами в одном ряду расстояние 10 метров. В каждом ряду высаживают разные виды плодовых деревьев. Через какое-то время с помощью аэросъемки определяют, какие саженцы прижились, а какие -- нет. Для успешного перекрестного опыления необходимо, чтобы дерево было на расстоянии не более 20 метров от прижившегося дерева того же вида, иначе оно не будет плодоносить. Определите, какое минимальное количество деревьев нужно посадить, чтобы все деревья могли плодоносить, и номер ряда, в котором необходимо дополнительно посадить максимальное количество деревьев.
Входные данные представлены в файле 26-80.txt следующим образом. В первой строке находится число N -- количество занятых мест натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер занятого места.
Запишите в ответе два числа: минимальное количество деревьев, которые нужно посадить в лесополосе, и номер ряда, где нужно посадить максимальное количество деревьев (если таких рядов несколько, нужно вывести номер первого из них).
Пример входного файла:
7
1 3
1 5
1 8
2 2
2 5
3 1
3 9
В этом случае достаточно посадить 4 дерева в позициях (1, 7), (2, 4), (3, 3) и (3, 7). Наибольшее количество деревьев (2) нужно посадить в 3-м ряду. Ответ: 4 3.