Задача 6 из 21

Разноцветные вложения

Время 2 с · память 256 МБ

Для упаковки подарка есть NN кубических коробок двух цветов. У каждой коробки известны длина стороны и цвет. Подарок упаковывают по принципу матрёшки: его кладут в одну из коробок, её — в другую коробку и так далее. Подарок помещается в любую коробку.

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

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

В первой строке находится число NN — количество коробок (натуральное число, не превышающее 10 00010\,000). Каждая из следующих NN строк содержит два натуральных числа: длину стороны коробки (не превышает 10 00010\,000) и номер её цвета (1 или 2).

Коробки идут в произвольном порядке; одинаковые коробки возможны.

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

Выведите два целых числа: сначала наибольшее количество коробок в одной упаковке, затем максимально возможную длину стороны самой маленькой коробки в такой упаковке.

Примеры

Ввод 1
5
8 1
12 2
16 1
20 2
11 2
Вывод 1
4 8
Ввод 2
5
21 2
30 1
17 1
29 2
25 1
Вывод 2
4 17

Примечание

В первом примере в упаковку входят коробки с длинами сторон 8, 12, 16 и 20: у соседних коробок длины сторон различаются на 4, а цвета разные. Коробку с длиной стороны 11 добавить нельзя: 11 отличается от 8 и от 12 меньше чем на 4.

Во втором примере самая большая коробка в искомую упаковку не входит. С ней можно использовать только три коробки: с длинами сторон 30, 21 и 17. Упаковка из коробок с длинами сторон 29, 25, 21 и 17 состоит из четырёх коробок.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче