After some time working at the library, you began to notice certain patterns. Namely, book number 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 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.
The first line contains one integer (1 \le n \le 10^6) — the number of books.
The next lines contain 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.
Print one integer — the answer to the problem.
Example 1
Example 2
It is guaranteed that solutions that work correctly for a_i = 1 will earn at least 50 points.