You have just been hired as FatalEagle's personal assistant! In addition to doing his math homework and writing his essays for him, your job description also includes planning out his anime marathons.
On this particular day, animes will be released. The -th anime is released on the -th minute and is minutes long . FatalEagle likes to watch animes as soon as they are released and he doesn't like to stop halfway through an episode to switch to another anime, this means that he will only watch the -th anime at the -th minute, and if he does, he will not be able to watch any animes that start in the following minutes. Having done your research online, you were also able to designate each of the animes a value , the happiness that the -th anime will bring your employer.
Since you want to make FatalEagle as happy as possible, find the maximum possible happiness he can have if you plan his anime marathon optimally.
Subtask 1 [20%]
(See Sample Input 1)
Subtask 2 [50%]
(See Sample Input 2)
Subtask 3 [30%]
(See Sample Input 3)
Warning: Fast I/O is highly recommended and even necessary for slower languages such as Java and Python. Check here for details.
The first line of input contains integer , the number of animes being released.
The -th line contains integers , and , the release time, length and happiness value of the -th anime, respectively. It is guaranteed that animes are given in non-decreasing order of .
One integer, the maximum amount of happiness possible for FatalEagle if you plan his marathon optimally.
Sample Input 1
5 1 2 3 2 1 5 3 1 3 4 2 4 5 1 5
Sample Output 1
Explanation for Sample Output 1
If FatalEagle always watches the next anime he can, he will watch animes , , and , leading to a total happiness value of . The optimal plan is to skip anime , watch and , skip , and watch , yielding the maximum possible happiness value of .
Sample Input 2
4 1 5 6 1 3 4 1 7 5 4 10 3
Sample Output 2
Explanation for Sample Output 2
The optimal plan is to watch animes and .
Sample Input 3
6 1 1000000000000 1000000000000 99999 99999 99999 123456 789 101112 416647 1333337 1000000000 416647 1 9988776655 99999999999 99999999999 99999999999
Sample Output 3
Explanation for Sample Output 3
Although anime requires tons of time investment, it's so good that FatalEagle will be content with only watching that anime.