题目描述

《梦三国2》是一款3D MOBA类网游。游戏继承《梦三国》的三国文化背景和基础玩法，并加入许多全新地图和全新竞技玩法。由于人气高，游戏在线人数与日俱增，我们知道当在线人数不断增长的时候，会给服务器带来巨大的压力。

已知该游戏中共有 $n$ 名用户，编号从 $1$ 到 $n$，服务器共有 $m$ 条服务线，每个用户最多只能登陆一条线，第 $i$ 条线最多可以容纳 $v[i]$ 名用户同时在线，且只能给编号在[$l[i]$,$r[i]$] 范围内的用户提供服务。现在希望找出一种合理的资源分配方案，使得同时在线人数最大化，请输出这个最大人数。

输入格式

输入共 $m+1$ 行。

第一行包括两个正整数 $n$，$m$。

接下来 $m$ 行，每行三个整数 $l[i],r[i],v[i]$。

输出格式

输出一个正整数，即最多容纳的用户数量。

样例输入输出

样例输入

5 3
1 1 1
2 4 2
2 3 2

样例输出

4

数据范围

对于 $100%$ 的数据，保证 $1 \le n,m \le 10000$。

样例解释

我们可以让 $1$ 号服务线服务用户 $1$，$2$ 号服务线服务用户 $4$，$3$ 号服务线服务用户 $2$ 和 $3$。