Description

Brett’s class will perform as follows: all $n$ students stand in a line, each holding a microphone, singing in unison the theme of "Pleasant Goat and Big Big Wolf" (this act looks a bit silly).

The class is divided into $m$ voice parts. Each voice part consists of consecutive students. The $i$-th voice part consists of students from $a_i$ to $b_i$ inclusive.

However, a student may belong to multiple voice parts, and some students may belong to none. To ensure singing quality, the $i$-th voice part must have at least $c_i$ students holding microphones (that is, the number of students holding microphones within the $i$-th voice part is at least $c_i$).

Please compute the minimum number of microphones that Brett’s class needs.

Input Format

The first line contains two positive integers $n, m$.

The next $m$ lines each contain three positive integers $a_i, b_i, c_i$.

Output Format

Output a single positive integer: the minimum number of microphones required to satisfy all constraints.

11 5 
3 7 3 
8 10 3 
6 8 1 
1 3 1 
10 11 1 

6 

Hint

For $100\%$ of the testdata, it is guaranteed that $n \le 30000$, $m \le 5000$, $1 \le a_i < b_i \le n$, and $c_i \le b_i - a_i + 1$.

Translated by ChatGPT 5