Problem I
Chemicals Monitoring

Victor works for Alberta Chemicals Monitoring (ACM). ACM is a company that analyses raw environmental data related to chemicals used in oil sand and other industries in Alberta, and produces some reports for environmental watchdogs.

Victor is in charge of a multi-processor cluster in ACM. Each processor is connected to a dedicated special purpose output generation unit (OGU). This cluster receives several raw data streams from field sensors and assigns each stream to a processor. Each processor performs some real time processing on a data stream and immediately after its termination, produces a report using its OGU.

Each stream has an integer starting time $s$, an integer duration $d$ and a priority $p$. This stream is active in the interval $[s, s+d)$ (right-open interval). The report of each stream must be produced immediately after its termination; otherwise, it will be useless. An OGU creates a report extremely fast, so you can assume that an OGU produces this report instantly.

In the past, at any instance of time, the number of data streams were not more than the number of processors and OGUs. So, Victor could process all data streams. Unfortunately, recently, in a suspicious power surge, all OGUs burnt out. Victor was able to salvage one OGU by using parts from the other OGUs. Now, he can no longer produce a report for all data streams and needs to choose a subset of them based on the priorities assigned to them. To handle access to this OGU, Victor restructured the cluster architecture as follows. When a stream starts, the system either admits or rejects it. If it admits a stream, the unique identifier of the processor assigned to this stream is pushed onto the stack. Only a processor having its identifier on top of the stack can use the OGU to produce its report. After production of the report, the processor identifier is popped from the stack. It should be noted that if some streams start at the same time, he can push their processor identifier in any order of his choice. Now, Victor needs your help to choose a subset of streams such that their reports can be generated with this single OGU. The total priority of the streams in the chosen subset should be maximized.

Input

The input consists of a single test case. The first line contains an integer $n$, where $n$ ($1 \le n \le 5\, 000$) is 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 the duration of the stream, and $p_ i$ is its priority. Note that the cluster has at least $5\, 000$ processors.

Output

Display the maximum total priority of a subset of streams such that their reports can be generated with the architecture described above using a single OGU.

4
1 3 6
2 5 8
3 3 5
5 3 6

13

6
5 4 10
3 4 6
1 8 100
3 2 3
4 2 4
3 2 2

115