Description

The roadside area is divided into blocks and numbered $1, 2, \ldots,n$. Each block has unit size and can contain at most one tree.

Each resident wants to plant some trees in front of their house and specifies three numbers $b$, $e$, $t$. These numbers mean that the resident wants at least $t$ trees in the area between $b$ and $e$ (inclusive of $b$ and $e$).

Different residents’ desired intervals may overlap. Your task is to find the minimum number of trees that can satisfy all requirements.

Input Format

The first line contains an integer, the number of areas $n$.

The second line contains an integer, the number of houses $h$.

Lines $3$ to $(h + 2)$ each contain three integers. On line $(i + 2)$, the integers are $b_i, e_i, t_i$, meaning the $i$-th resident wants at least $t_i$ trees between $b_i$ and $e_i$.

Output Format

Output a single integer, the minimum number of trees.

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

5

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $1 \leq n \leq 3 \times 10^4$，$1 \leq h \leq 5 \times 10^3$。
• $1 \leq b_i \leq e_i \leq n$，$1 \leq t_i \leq e_i - b_i + 1$。

Translated by ChatGPT 5