Разработчики игр придумали новую игру – «Башня Сосруко». Суть игры заключается в том, что нужно построить башню из прямоугольных каменных плит, каждая из которых задается шириной и высотой. Одну плиту можно поставить на другую, если ширина нижней плиты строго больше ширины верхней. Самой нижней плитой в башне может быть плита любой ширины разработчикам определить по заданному набору плит, какой наибольшей высоты башню можно построить.

Формат входных данных

В первой строке входных данных задается число N – количество плит (1£ N £100000).

В следующих N строках задаются пары целых чисел wi и hi (1£ wi, hi £109), разделенные пробелом – ширина и высота плиты, соответственно.

Формат выходных данных

Целое число – максимальная высота башни.

Замечание

В приведенном примере башня будет состоять из двух плит: нижней будет плита с номером 3, а верхней – плита с номером 2. Плиту с номером 1 нельзя использовать для построения башни, т.к. её ширина совпадает с шириной нижней плиты.

Chillin    3   14.12.2020 11:43    2