元旦晚会
题目背景
玛雅人预言的世界末日没有发生,我们迎来了地球的第五个太阳纪。
学校将要举办第五个太阳纪的第一次元旦晚会。Brett 的班级要参加,并且还表演节目。
题目描述
Brett 班的节目是这样的:全班 $n$ 个同学排成一排,同学们手拿话筒,齐唱《喜洋洋与灰太狼》(这个节目看起来有点二) 。
Brett 班的同学分成了 $m$ 个声部,一个声部由连续的同学组成,第 $i$ 个声部由 $a_i$ 到 $b_i$ 之间的同学组成(包括 $a_i$ 和 $b_i$ )
但是一个同学有可能同时属于多个声部,且有可能有同学不属于任何一个声部。为了保证演唱效果,第 $i$ 个声部必须至少有 $c_i$ 个同学持有话筒(即第 $i$ 个声部持有话筒的同学数大于等于 $c_i$)。
请你算出 Brett 班最少需要几个话筒。
输入输出格式
输入格式
第一行 $2$ 个正整数 $n,m$。
以下 $m$ 行,每行 $3$ 个正整数 $a_i, b_i, c_i$。
输出格式
一个正整数表示满足要求的最少话筒数。
输入输出样例
输入样例 #1
11 5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
输出样例 #1
6
说明
对于 $100\%$ 的数据,保证 $n \le 30000$,$m \le 5000$,$1 \le a_i < b_i \le n$,$c_i \le b_i - a_i + 1$。