Ханойская фабрика
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наверняка вы слышали об известной задаче про Ханойские башни, но мало кто знает, что существует целая фабрика, производящая кольца для этой замечательной игры. Однажды на эту фабрику пришел срочный заказ от властителя Египта — Солнцеликого. Солнцеликий требует немедленно прислать ему для игры как можно более высокую башню. Работники фабрики не были готовы к такому необычному заказу, поэтому им придётся собрать какую-то башню из уже произведённых колец.

На складах фабрики находятся n колец, i-е кольцо имеет внутренний радиус ai, внешний радиус bi и высоту hi. Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия:

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

В первой строке входных данных записано целое число n (1 ≤ n ≤ 100 000) — количество колец на складах фабрики.

В i-й из последующих n строк записаны три числа ai, bi и hi (1 ≤ ai, bi, hi ≤ 109, bi > ai) — внутренний радиус, внешний радиус и высота i-го кольца соответственно.

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

Выведите максимальную высоту башни, которую смогут получить работники фабрики.

Примеры

Входные данные
3
1 5 1
2 6 2
3 7 3
Выходные данные
6
Входные данные
4
1 2 1
1 3 3
4 6 2
5 7 1
Выходные данные
4

Примечание

В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке 3, 2, 1.

Во втором примере можно либо поставить кольцо 3 на кольцо 4 и получить башню высоты 3, либо поставить кольцо 1 на кольцо 2 и получить башню высоты 4.

Система оценки

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.

Решение, корректно работающие при 1 ≤ n ≤ 9, наберут не менее 10 баллов.

Решение, корректно работающие при 1 ≤ n ≤ 15, наберут не менее 20 баллов.

Решение, корректно работающие при 1 ≤ n ≤ 1000, наберут не менее 60 баллов.