题目描述

现在有 $n$ 个蛋糕排成一列，编号分别为 $1\sim n$，同时有 $m$ 位小马，第 $i$ 位小马喜欢吃编号在 $[l_i,r_i]$ 中的蛋糕（没有两匹小马会喜欢相同范围的蛋糕）。

遗憾的是，狡黠的小马们会在轮到自己时将自己喜欢的所有蛋糕全部吃掉（如果没有她就吃不到了），如果她成功的吃到了至少一个蛋糕，那么她会获得 $w_i$ 的满足值。

现在派对小马 pinkie pie 将要给小马们安排一个吃蛋糕的顺序，使她们获得的满足值之和最大。

输入格式

第一行包含两个正整数 $n,m$；

接下来 $m$ 行，每行三个正整数 $w_i,l_i,r_i$。

输出格式

输出最大可能的满足值之和。

样例

Input # 1

2 2
100 1 2
100 1 1

Output # 1

200

数据范围与提示

对于 $10\%$ 的数据，有 $m\le 9$.

对于 $30\%$ 的数据，有 $m\le 20$.

对于 $60\%$ 的数据，有 $n\le 50$.

对于 $100\%$ 的数据，有 $1 \le n \le 300,1 \le m \le \dfrac{n(n-1)}{2},1 \le l_i\le r_i \le n,1 \le w_i \le 10^6$，且任取 $i\not=j$, 有 $(l_i,r_i)\not=(l_j,r_j)$.