Моніторинг Хімічних Речовин
Віктор працює в компанії Alberta Chemicals Monitoring (ACM), яка займається аналізом необроблених екологічних даних, пов'язаних з хімікатами, що використовуються в нафтових пісках та інших галузях в Альберті, і створює звіти для екологічних наглядових органів.
Віктор відповідає за кластер з багатьма процесорами в ACM. Кожен процесор підключений до спеціального блоку генерації виходу (OGU). Цей кластер отримує кілька потоків необроблених даних з польових датчиків і призначає кожен потік процесору. Кожен процесор виконує обробку даних у реальному часі і відразу після завершення створює звіт за допомогою свого OGU.
Кожен потік має цілий час початку s, цілу тривалість d і пріоритет p. Цей потік активний в інтервалі [s, s + d) (право-відкритий інтервал). Звіт по кожному потоку має бути створений відразу після його завершення; інакше він буде марним. OGU створює звіт надзвичайно швидко, тому можна вважати, що OGU створює цей звіт миттєво.
У минулому, в будь-який момент часу, кількість потоків даних не перевищувала кількість процесорів і OGU. Тому Віктор міг обробляти всі потоки даних. На жаль, нещодавно, під час підозрілого стрибка напруги, всі OGU згоріли. Віктору вдалося врятувати один OGU, використовуючи частини з інших OGU. Тепер він більше не може створювати звіти для всіх потоків даних і повинен вибрати підмножину з них на основі пріоритетів, призначених їм. Щоб керувати доступом до цього OGU, Віктор реорганізував архітектуру кластера наступним чином. Коли потік починається, система або приймає, або відхиляє його. Якщо вона приймає потік, унікальний ідентифікатор процесора, призначеного цьому потоку, додається в стек. Тільки процесор, ідентифікатор якого знаходиться на вершині стека, може використовувати OGU для створення свого звіту. Після створення звіту ідентифікатор процесора видаляється зі стека. Слід зазначити, що якщо деякі потоки починаються одночасно, він може додати їх ідентифікатори процесорів у будь-якому порядку на свій вибір. Тепер Віктору потрібна ваша допомога, щоб вибрати підмножину потоків, звіти яких можуть бути створені за допомогою цього єдиного OGU. Загальний пріоритет потоків у вибраній підмножині повинен бути максимальним.
Вхідні дані
Вхідні дані складаються з одного тестового випадку. Перша строка містить ціле число n, де n (1 ≤ n ≤ 5000) — це кількість потоків даних. Кожна з наступних n строк містить три цілі числа s_i, d_i, p_i (1 ≤ s_i, d_i ≤ 10^9, 0 ≤ p_i ≤ 100000), що описують один потік даних, де s_i — це час початку, d_i — це тривалість потоку, а p_i — це його пріоритет. Зазначимо, що кластер має щонайменше 5000 процесорів.
Вихідні дані
Виведіть максимальний загальний пріоритет підмножини потоків, звіти яких можуть бути створені з використанням описаної вище архітектури з одним OGU.