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