На научной смене Алекс может посетить n лабораторных сеансов. Сеанс i начинается в момент sᵢ, заканчивается в момент fᵢ и приносит vᵢ исследовательских баллов. Баллы начисляются только за полностью посещённый сеанс.
Нельзя участвовать в двух сеансах одновременно. При этом сразу после окончания одного сеанса можно начать другой: если первый заканчивается в момент x, второй может начаться в момент x. Переходы между лабораториями времени не занимают.
Алекс может выбирать любые сеансы и пропускать остальные. Найдите максимальную сумму баллов.
Входные данные
Первая строка содержит целое число n (1 ≤ n ≤ 200 000). Следующие n строк содержат по три целых числа sᵢ, fᵢ, vᵢ (0 ≤ sᵢ < fᵢ ≤ 109, 1 ≤ vᵢ ≤ 109). Сеансы перечислены в произвольном порядке; совпадения времён допускаются.
Выходные данные
Выведите максимальное количество баллов, которое сможет набрать Алекс.
Пояснения к примерам
Пример 1. Подходят сеансы 1, 3 и 5: 7 + 9 + 10 = 26 баллов.
Пример 2. Окончание первого совпадает с началом второго; можно посетить оба.
| № | Входные данные | Выходные данные |
|
1
|
6
1 3 7
2 5 12
3 6 9
5 7 8
6 9 10
1 9 24
|
26
|
|
2
|
2
0 2 4
2 3 6
|
10
|