PROGRAMMING:Planting trees
There are several houses on one side of a street. For environmental protection reasons, residents want to plant some trees on the roadside. The roadside area is divided into n blocks and numbered as 1... N. each block is a unit size and can grow up to one tree. Each resident wants to plant some trees in front of the door and specifies three numbers B, e and t. these three numbers respectively indicate that the resident wants to plant at least t trees between B and E. of course, B ≤ E and t ≤ E-B + 1 allow the sub areas where the resident wants to plant trees to cross. Due to the shortage of funds, the environmental protection department asks you to find out the minimum number of trees that can meet the planting requirements of all residents.
###Input format:
The first line, N, represents the number of regions.
The second line h is the number of houses.
The following h line describes the needs of residents: B, e and t (0 < B ≤ e ≤ 30000, t ≤ E-B + 1) are separated by a space.
###Output format:
Output a number, in order to meet the requirements of all residents, the minimum number of trees to be planted.
###Input example:
```in
nine
four
1 4 2
4 6 2
8 9 2
3 5 2
```
###Output example:
```out
five
```
###Data size:
30% of the data meet 0 < n ≤ l 000; 0100% of the data satisfy n ≤ 30 000; h≤5 000, 0
answer：If there is no answer, please comment
[problem solving ideas]
If you want to plant less trees, you need to make one tree be used by multiple intervals. In this way, try to plant trees in the overlapping interval, and the overlapping position must be at the end of the interval. When we deal with the problem, we first sort all the intervals according to their ending positions, and then deal with each interval in turn. First, we plant trees that meet the requirements at the end of the first interval. For the next interval, we will plant trees at the end of the interval according to the difference.
[algorithm steps]
① Quick sort by end position first.
② Each interval is dealt with in turn.
a. Scan the interval from front to back and count the number of selected points.
b. If the number of selected points exceeds the required number, continue.
c. Otherwise, scan from back to front to add missing coverage points.
③ Output ANS.
###Input format:
The first line, N, represents the number of regions.
The second line h is the number of houses.
The following h line describes the needs of residents: B, e and t (0 < B ≤ e ≤ 30000, t ≤ E-B + 1) are separated by a space.
###Output format:
Output a number, in order to meet the requirements of all residents, the minimum number of trees to be planted.
###Input example:
```in
nine
four
1 4 2
4 6 2
8 9 2
3 5 2
```
###Output example:
```out
five
```
###Data size:
30% of the data meet 0 < n ≤ l 000; 0
answer：If there is no answer, please comment
[problem solving ideas]
If you want to plant less trees, you need to make one tree be used by multiple intervals. In this way, try to plant trees in the overlapping interval, and the overlapping position must be at the end of the interval. When we deal with the problem, we first sort all the intervals according to their ending positions, and then deal with each interval in turn. First, we plant trees that meet the requirements at the end of the first interval. For the next interval, we will plant trees at the end of the interval according to the difference.
[algorithm steps]
① Quick sort by end position first.
② Each interval is dealt with in turn.
a. Scan the interval from front to back and count the number of selected points.
b. If the number of selected points exceeds the required number, continue.
c. Otherwise, scan from back to front to add missing coverage points.
③ Output ANS.