Book rental

After some time working at the library, you began to notice certain patterns. Namely, book number $i$ has an interest value of $a_i$ and to read it you need to spend $l_i$ time. Since you love reading so much, you can only take the next book when you have completely finished reading the previous one. Also, all books are very popular — as soon as a book becomes available, someone else takes it. It is known that book number $i$ becomes available at time $t_i$, and if you don't start reading the book at time $t_i$, someone else will take it. Tell us the maximum sum of interest values of books that you can read.

Input

The first line contains one integer $n$ ($1\le n\le 10^6$) — the number of books.

The next $n$ lines contain $3$ integers $t_i$, $l_i$, $a_i$ ($1\le t_i,l_i\le 10^6$, $1\le a_i\le 10^9$) — descriptions of the books.

Output

Print one integer — the answer to the problem.

Examples

Scoring

It is guaranteed that solutions that work correctly for $a_i=1$ will earn at least 50 points.