Description

笨笨种了一块西瓜地，但这块西瓜地的种植范围是一条直线的……

笨笨在一番研究过后，得出了 $m$ 个结论，这 $m$ 个结论可以使他收获的西瓜最多。

笨笨的结论是这样的：

从西瓜地 $b$ 处到 $e$ 处至少要种植 $t$ 个西瓜，这个范围的收获就可以最大化。

笨笨不想那么辛苦，所以他想种植的西瓜尽量少，而又满足每一个所得的结论。

Input Format

第一行两个数 $n$, $m$（$0<n \le 5000$，$0 \le m\le 3000$），表示笨笨的西瓜地长 $n$，笨笨得出 $m$ 个结论。

接下来 $m$ 行表示笨笨的 $m$ 个结论，每行三个数 $b$, $e$, $t$（$1 \le b\le e\le n$，$0 \le t\le e-b+1$）。

Output Format

输出笨笨最少需种植多少西瓜。

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

5

Hint

基本上来说，笨笨的西瓜地就是一条壮观的线……