Перед святами Шеф отримує дуже багато запрошень на святкові заходи. Щоб краще планувати свій час, Шеф увів правило, щоб у кожному запрошенні був чітко вказаний відрізок часу ~[a_i; b_i]~, коли триває захід. Крім того, сам Шеф призначає кожному заходу важливість ~c_i~. Шеф не любить половинчатих рішень, тому або перебуває на заході увесь вказаний час, або не приходить на нього зовсім. Між відвідинами заходів має бути хоча б мінімальна перерва, тобто Шеф може встигнути на ~j~-й (за списком запрошень) після ~i~-го тоді й тільки тоді, коли ~a_j > b_i~. Напишіть програму, що допомагатиме Шефу вибрати заходи, які він відвідає, так, щоб сума важливостей вийшла максимальною можливою.

Вхідні дані

Програма читає спочатку кількість заходів ~N~, потім ~N~ трійок ~a_i\,\,b_i\,\,c_i~ (кожна трійка в окремому рядку). Гарантовано, що всі ці числа цілі додатні, ~a_i < b_i \leqslant 10^9~, сума всіх ~c_i~ не перевищує ~10^9~.

Обмеження

У першому блоці тестів, ~1\leqslant N\leqslant 1000~. У другому блоці тестів, ~10^4\leqslant N\leqslant 10^5~.

Результати

Програма має вивести єдине число – максимально можливу сумарну важливість заходів, які можливо вибрати для відвідання.

Приклади

Вхід

3
1 5 3
5 9 5
6 11 2

Результат

5

Примітка

В цьому тесті, однакову суму 5 можна набрати двома способами: або вибравши перший і останній заходи (тоді сумарна важливість виявляється 3+2=5), або вибравши лише 2-й з цих трьох (він один має ту саму важливість 5).