화학물질 모니터링

빅터는 앨버타 화학물질 모니터링(ACM)에서 일한다. ACM은 앨버타의 오일샌드 산업을 비롯한 여러 산업에서 쓰는 화학물질의 환경 원시 데이터를 분석해 환경 감시 기관에 낼 보고서를 만드는 회사다.

빅터가 맡은 일은 ACM의 다중 프로세서 클러스터 관리다. 프로세서마다 보고서 생성 전용 장치(OGU)가 하나씩 붙어 있다. 클러스터는 현장 센서에서 들어오는 원시 데이터 스트림을 여러 개 받아 스트림마다 프로세서를 하나씩 배정한다. 프로세서는 배정받은 스트림을 실시간으로 처리하고, 스트림이 끝나는 순간 자기 OGU로 보고서를 만든다.

스트림에는 정수 시작 시각 $s$, 정수 지속 시간 $d$, 우선순위 $p$가 있다. 스트림은 오른쪽이 열린 구간 $[s, s+d)$ 동안 활성 상태다. 보고서는 스트림이 끝나는 순간 바로 만들어야 하고, 그 순간을 놓치면 쓸모가 없어진다. OGU는 보고서를 아주 빠르게 만들기 때문에 만드는 데 걸리는 시간은 0이라고 봐도 된다. 그래서 같은 시각에 끝나는 스트림이 여럿이면 스택 순서대로 보고서를 잇달아 만들면 된다.

예전에는 어느 시점에도 스트림 수가 프로세서와 OGU 수를 넘지 않아서 빅터는 모든 스트림을 처리할 수 있었다. 그런데 최근 원인 모를 과전압으로 OGU가 전부 타 버렸고, 빅터는 남은 부품을 긁어모아 OGU 하나만 되살렸다. 이제는 모든 스트림의 보고서를 만들 수 없으니 우선순위를 보고 일부만 골라야 한다.

하나 남은 OGU를 나눠 쓰려고 빅터는 클러스터 구조를 이렇게 바꿨다. 스트림이 시작하면 시스템은 그 스트림을 받아들이거나 거절한다. 받아들이면 그 스트림을 맡은 프로세서의 고유 번호를 스택에 넣는다. 스택 맨 위에 번호가 올라와 있는 프로세서만 OGU로 보고서를 만들 수 있고, 보고서를 만들고 나면 그 번호를 스택에서 빼낸다. 여러 스트림이 같은 시각에 시작하면 프로세서 번호를 넣는 순서는 빅터가 원하는 대로 정할 수 있다.

이 구조에서 보고서를 전부 만들어 낼 수 있는 스트림 부분집합 가운데 우선순위 합이 가장 큰 값을 구하라.

입력은 테스트 케이스 하나로 이루어진다. 첫 줄에 데이터 스트림의 개수 $n$ ($1 \le n \le 5000$)이 주어진다. 이어지는 $n$개의 줄에는 스트림 하나를 나타내는 세 정수 $s_i$, $d_i$, $p_i$ ($1 \le s_i, d_i \le 10^9$, $0 \le p_i \le 100\,000$)가 주어진다. $s_i$는 시작 시각, $d_i$는 지속 시간, $p_i$는 우선순위다. 클러스터의 프로세서는 5000개 이상이다.

위에서 설명한 구조로 OGU 하나만 써서 보고서를 모두 만들 수 있는 스트림 부분집합의 우선순위 합 중 최댓값을 출력한다.