Problems
Apprentice Learning Trajectory
Apprentice Learning Trajectory
Abigail is an apprentice studying to become a blacksmith. She wants to plan her learning trajectory and make as many swords as possible on her way to becoming a famous expert.
There are $n$ masters willing to host her as their apprentice. The $i$-th master will start working at the minute $a_i$ and end working at the minute $b_i$, working for a total of $b_i - a_i$ minutes. During this interval of time, Abigail can work at this master's forge. She can enter and leave the forge several times and produce one or several swords upon each arrival. However, in order to produce a sword under supervision of the $i$-th master she has to work there for $t_i$ minutes in a row. She can't leave the sword unfinished and
continue working on it upon her next arrival to this forge.
Help Abigail make an optimal plan and calculate the maximum number of swords she can produce under the supervision of $n$ masters.
\InputFile
The first line contains integer $n~(1 \le n \le 2 \cdot 10^5)$ --- the number of masters.
Each of the next $n$ lines contains three integers $a_i, b_i, t_i~(1 \le a_i < a_i + t_i \le b_i \le 10^{18})$ --- the start and the end time of master's work, and the time needed to make one sword in their forge.
\OutputFile
Output the maximum number of swords Abigail can produce using the optimal learning trajectory.
\includegraphics{https://static.e-olymp.com/content/cc/ccd8a565af0b9e6a6d07fd9fbaeb0107385889b0.gif}
Input example #1
2 5 7 1 1 9 2
Output example #1
5
Input example #2
3 1 10 4 6 12 3 9 13 2
Output example #2
4
Input example #3
3 1 13 4 6 11 2 9 13 3
Output example #3
4