P1986 New Year’s Day Gala

The Mayan doomsday prophecy did not come true, and we have welcomed the Fifth Sun era of Earth. The school is going to hold the first New Year’s Day gala of the Fifth Sun era. Brett’s class will participate and perform.

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.

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 a single positive integer: the minimum number of microphones required to satisfy all constraints.

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