Задача: ПИРАМИДА
Для строительства двухмерной пирамиды используются прямоугольные блоки, каждый из которых характеризуется шириной и высотой. Можно поставить один блок на другой, только если ширина верхнего блока строго меньше ширины нижнего. Самым нижним в пирамиде может быть блок любой ширины.
По заданному набору блоков требуется определить, пирамиду какой наибольшей высоты можно построить из них.
Формат входных данных
В первой строке входных данных задается число N – количество блоков ( 1 <= N <= 100000 ). В следующих N строках задаются пары целых чисел wi и hi ( 1<= wi , hi <= 109), разделенные пробелом – ширина и высота блока, соответственно.
Формат выходных данных
Целое число – максимальная высота пирамиды.
| Ввод |
Вывод |
3
3 1
2 2
3 3 |
5 |
Замечание.
В приведенном примере пирамида будет состоять из двух блоков: нижним будет блок с номером 3, а верхним – блок с номером 2. Блок с номером 1 нельзя использовать для строительства пирамиды, т.к. его ширина совпадает с шириной нижнего блока.
Ваш ответ: