该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

dash星球毕业欢送会过后，小蓝老师要为班上的 $n$ 名大学毕业生分配相应的工作岗位，于是他联系了 $m$ 家公司，每名学生最多会去其中 $1$ 家公司工作。当然，这些公司并不是学生想去就能去的，每家公司都有相应的能力考核标准，每名学生也有一个综合能力排名，学生需要符合公司的能力考核标准才能进入到公司工作。

确切的说，$n$ 名学生中第 $i$ 个学生的综合能力排名即为 $i (1≤i≤n)$，$m$ 家公司中的第 $j$ 家公司的能力考核标准是一个区间 $[l_j, r_j](1\leq l_j\leq r_j \leq n)$，表示这家公司只会招收综合能力排名在 $[l_j, r_j]$ 的学生，并且公司的员工薪水为 $w_i$。

现在需要选择几家公司，并且确定它们的选取顺序。假设选了 $k$ 家公司，选取顺序分别为 $c_1, c_2, ..., c_k$。对于第 $c_1$ 家公司来说，它会选走 $[l_{c_1}, r_{c_1}]$ 的所有学生；对于第 $c_2$ 家公司来说，它会选走 剩余 $[l_{c_2}, r_{c_2}]$ 的所有学生。这 $k$ 家公司按顺序选取，需要保证每一家公司至少能够招到 $1$ 名学生。

问：在满足上述条件的前提下，最大的 $\sum\limits_{i=1}^k w_{c_i}$ 是多少？

注意：

• $1$ 名学生最多会去其中 $1$ 家公司工作， 被选中的公司至少能够招收 $1$ 名学生。
• 学生可以没有工作，未被选中的公司不招收员工。
• 所有公司的考核标准区间两两不相同。

输入格式

第一行两个数字 $n,m$，表示学生数量与公司数量。

接下来 $m$ 行是 $m$ 家公司的信息，每行 $3$ 个正整数 $w_j, l_j, r_j$，表示第 $j$ 家公司的信息。

输出格式

一个正整数，表示最大的 $\sum\limits_{i=1}^k w_{c_i}$。

样例

1 1
4 1 1

4

3 4
700 1 1 
500 1 3
1100 3 3
300 2 2

2300

7 11
2178 1 7
76532 1 2
114514 2 4
314159 3 7
89757 2 3
141414 5 7
173258 2 2
89162 4 5
71354 5 6
90317 4 7
561283 2 5

1400857

数据范围

• 第 $1\sim 4$ 个测试点： $1≤n,m≤10$
• 第 $5\sim 10$ 个测试点：
  • $1≤n≤50$
  • 其中 $5\sim 7$ 个测试点：$1≤m≤20$
• 第 $11∼20$ 个测试点： $1≤n≤300$
• 对于所有的测试点，均满足：
  • $1\leq m\leq \frac{n\cdot(n+1)}{2}$
  • $1\leq l_i\leq r_i\leq n$
  • $1\leq w_i\leq 1000000$