Apprentice Learning Trajectory

Time limit3sMemory limit512 MB

Summary

Given n masters, each with a work window [a_i, b_i] and a sword time t_i, find the most non-overlapping sword segments, each of length t_i inside one window.

Level: Hard8 of 10
Topics: Dynamic programming, Intervals, Greedy
Solved: No attempts yet

Problem

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 starts working at minute $a_i$ and stops at minute $b_i$ , so the master works for $b_i - a_i$ minutes in total. During this interval, 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. To produce a sword under the $i$ -th master's supervision, she must work there for $t_i$ minutes in a row. She cannot leave a sword unfinished and continue it on her next visit to the same forge.

Help Abigail make an optimal plan and calculate the maximum number of swords she can produce under the supervision of the $n$ masters.

Input

The first line contains an integer $n$ ( $1 \le n \le 200\,000$ ), the number of masters.

Each of the next $n$ lines contains three integers $a_i$ , $b_i$ , and $t_i$ ( $1 \le a_i < a_i + t_i \le b_i \le 10^{18}$ ), the start time, end time, and the time needed to make one sword at the $i$ -th master's forge.

Output

Output the maximum number of swords Abigail can produce using an optimal learning trajectory.

Examples3

Example 1
Input
```
2
5 7 1
1 9 2
```
Expected output
```
5
```
Example 2
Input
```
3
1 10 4
6 12 3
9 13 2
```
Expected output
```
4
```
Example 3
Input
```
3
1 13 4
6 11 2
9 13 3
```
Expected output
```
4
```