Наверняка вы слышали об известной задаче про Ханойские башни, но мало кто знает, что существует целая фабрика, производящая кольца для этой замечательной игры. Однажды на эту фабрику пришел срочный заказ от властителя Египта — Солнцеликого. Солнцеликий требует немедленно прислать ему для игры как можно более высокую башню. Работники фабрики не были готовы к такому необычному заказу, поэтому им придётся собрать какую-то башню из уже произведённых колец.
На складах фабрики находятся \(n\) колец, \(i\)-е кольцо имеет внутренний радиус \(a_i\), внешний радиус \(b_i\) и высоту \(h_i\). Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия:
-
Внешние радиусы колец образовывали невозрастающую последовательность, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j \leq b_i\).
-
Кольца не должны проваливаться друг в друга, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j > a_i\).
-
Суммарная высота всех использованных колец должна быть максимальна.
Формат входных данных
В первой строке входных данных записано целое число \(n\) (\(1 \leq n \leqslant 100\,000\)) — количество колец на складах фабрики.
В \(i\)-й из последующих \(n\) строк записаны три числа \(a_i\), \(b_i\) и \(h_i\) (\(1 \leq a_i, b_i, h_i \leq 10^9\), \(b_i > a_i\)) — внутренний радиус, внешний радиус и высота \(i\)-го кольца соответственно.
Формат выходных данных
Выведите максимальную высоту башни, которую смогут получить работники фабрики.
Замечание
В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке \(3\), \(2\), \(1\).
Во втором примере можно либо поставить кольцо \(3\) на кольцо \(4\) и получить башню высоты \(3\), либо поставить кольцо \(1\) на кольцо \(2\) и получить башню высоты \(4\).
В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.
Решение, корректно работающие при \(1 \leq n \leq 9\), наберут не менее \(10\) баллов.
Решение, корректно работающие при \(1 \leq n \leq 15\), наберут не менее \(20\) баллов.
Решение, корректно работающие при \(1 \leq n \leq 1000\), наберут не менее \(60\) баллов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 5 1
2 6 2
3 7 3
|
6
|
|
2
|
4
1 2 1
1 3 3
4 6 2
5 7 1
|
4
|