P1250 Planting Trees

On one side of a street there are several houses. For environmental reasons, the residents want to plant some trees along the roadside.

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.

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 a single integer, the minimum number of trees.

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