Description

A street is divided into $n$ segments, numbered consecutively from $1$ to $n$. Each segment can plant at most one tree. Residents have provided $h$ sets of suggestions, each consisting of three integers $b$, $e$, and $t$, indicating that residents wish to plant at least $t$ trees between segments $b$ and $e$ (inclusive). The intervals suggested by these recommendations may overlap. The question is: what is the minimum number of trees that need to be planted to satisfy all residents' suggestions?

Input Format

The first line contains $n$, the number of street segments.

The second line contains $h$, the number of suggestions.

The following $h$ lines each describe a suggestion with three integers: $b$, $e$, $t$, separated by spaces.

Output Format

Output a single integer representing the minimum number of trees required to meet all residents' suggestions.

Sample 1

9
4
1 4 2
4 6 2
8 9 2
3 5 2

5

Data Range and Hints

For $30\%$ of the data, $0<n\le 1000$ and $0<h\le 500$;

For $100\%$ of the data, $0<n\le 3\times 10^4$, $h\le 5000$, $0<b\le e\le 3\times 10^4$, and $t\le e-b+1$.