Задача E. Пирамида
Задачу добавил: alef
Успешно сдано решений: 5
Время на тест 5 с, память 256 Мб
Отдел RRR занимается изготовлением материалов с нетрадиционными оптическими свойствами. Для одного эксперимента им потребовалось изготовить пирамиду. Пирамида изготавливается из тонких прямоугольных пластин разного размера. Пластины должны быть уложены таким образом, чтобы любая пластина, расположенная выше, целиком помещалась на пластине, расположенной ниже. Стороны пластин при этом должны быть параллельны. Более того, чтобы получить нужные оптические свойства, пластины вообще нельзя поворачивать: т.е. «длина» должна быть параллельная «длине», а «ширина» — «ширине».
Сотрудникам отдела задача укладки пластин в пирамиду показалась весьма простой, и они поручили ее практикантам. Практиканты запрограммировали нанороботов, которые укладывали эти пластины, не совсем правильно, и вместо пирамиды получилась довольно неровная стопка пластин. Дело осложняется тем, что разобрать стопку, не повредив пластины, уже не получится, поскольку для их соединения использовали наноклей.
Однако сотрудники отдела QQQ в ходе своих экспериментов изобрели кислоту, которая способна выжечь такую пластину, но совершенно не воздействует на наноклей. Таким образом, из стопки можно удалить любые пластины.
Теперь сотрудники отдела RRR обратились к Кеше с просьбой написать новую программу для нанороботов, которая позволит из имеющейся стопки пластин получить пирамиду максимально возможной высоты.
Формат входного файла input.txt
Первая строка — целое число N, 1 ≤ N ≤ 105 — количество пластин.
Каждая из следующих N строк содержит пару чисел Aj и Bj (0 <= Aj, Bj <= 5∙108) — длина и ширина пластины # j. Пластина # j будет считаться полностью помещающейся на пластине # k, если одновременно выполняются условия Aj < Ak и Bj < Bk.
Формат выходного файла output.txt
Первая строка — целое число, максимально возможное количество пластин, которые можно оставить в стопке, чтобы получить из нее пирамиду.
Пример входного файла — 1
3
3 3
2 2
1 1
Пример выходного файла — 1
1
Пример входного файла — 2
10
1 1
2 4
3 3
4 2
5 3
3 5
6 5
5 6
7 7
5 3
Пример выходного файла — 2
5