Мониторинг химических веществ
Виктор работает в компании Alberta Chemicals Monitoring (ACM). 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.