Chemicals Monitoring

Victor works for Alberta Chemicals Monitoring (ACM). ACM analyses raw environmental data on the chemicals used by the oil sand industry and other industries in Alberta, and writes reports for environmental watchdogs.

Victor runs the multi-processor cluster at ACM. Every processor is wired to its own output generation unit (OGU). The cluster receives several raw data streams from field sensors and assigns each stream to one processor. A processor handles its stream in real time and produces a report with its OGU the moment the stream ends.

A stream has an integer start time $s$, an integer duration $d$ and a priority $p$. The stream is active during the right-open interval $[s, s+d)$. Its report must be produced the instant the stream ends, otherwise the report is useless. An OGU creates a report extremely fast, so you can assume the report takes no time at all. Several streams that end at the same instant therefore get their reports one after another in stack order.

In the past the number of data streams at any instant never exceeded the number of processors and OGUs, so Victor could process every stream. In a recent power surge of unknown origin all OGUs burnt out, and Victor rebuilt a single working OGU from the salvaged parts. He can no longer produce a report for every stream, so he has to pick a subset of them by priority.

To share the one remaining OGU, Victor restructured the cluster as follows. When a stream starts, the system either admits it or rejects it. If it admits the stream, the unique identifier of the processor assigned to that stream is pushed onto a stack. Only the processor whose identifier sits on top of the stack can use the OGU to produce its report, and that identifier is popped once the report is out. If several streams start at the same time, Victor can push their processor identifiers in any order he likes.

Find the largest total priority of a subset of streams whose reports can all be produced under this architecture.

The input consists of a single test case. The first line contains an integer $n$ ($1 \le n \le 5000$), the number of data streams. Each of the next $n$ lines contains three integers $s_i$, $d_i$, $p_i$ ($1 \le s_i, d_i \le 10^9$, $0 \le p_i \le 100\,000$) describing one data stream, where $s_i$ is its start time, $d_i$ is its duration and $p_i$ is its priority. The cluster has at least 5000 processors.

Print the maximum total priority of a subset of streams whose reports can all be generated by the single OGU under the architecture described above.