Background

Benben: Little watermelons, little watermelons~

Passer-by A: No way. These watermelons are clearly big...

Benben: Then... big watermelons, big watermelons~

Passer-by A: You changed your words so fast...

Benben: Watermelons, watermelons~ Cute watermelons~

Problem Description

Benben planted a watermelon field, but the planting area of this field is a straight line...

After some research, Benben came up with $m$ conclusions. These $m$ conclusions can maximize the number of watermelons he harvests.

Benben's conclusions are as follows:

From position $b$ to position $e$ in the field, at least $t$ watermelons must be planted, and then the harvest in this range can be maximized.

Benben does not want to work that hard, so he wants to plant as few watermelons as possible, while satisfying every conclusion he obtained.

Input Format

The first line contains two numbers $n$ and $m$ ($0<n \le 5000$, $0 \le m\le 3000$), meaning Benben's watermelon field has length $n$, and Benben has obtained $m$ conclusions.

The next $m$ lines describe Benben's $m$ conclusions. Each line contains three numbers $b$, $e$, $t$ ($1 \le b\le e\le n$, $0 \le t\le e-b+1$).

Output Format

Output the minimum number of watermelons Benben needs to plant.

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

5

Hint

Basically, Benben's watermelon field is a spectacular line...

Translated by ChatGPT 5