题目描述

终于，科尔沃的闪烁法术不再是用来瞬移了！他打算用来消灭界外魔留下的符文~

科尔沃面前从左至右一共放有 $n$ 个界外魔的符文，编号 $1 \sim n$。同时，他也准备了 $m$ 个闪烁法术，编号 $1 \sim m$。每个闪烁法术会摧毁一段连续的符文。其中闪烁法术 $i$ 会破坏编号范围 $[l_i, r_i]$ 的符文（包括编号 $l_i$ 和 $r_i$)并回复 $b_i$ 的魔力值，任意两个闪烁法术所破坏的符文的编号范围都不同，且魔力值的回复具有累加效应。

显然，每个符文不可能被破坏多次。因此，要想一个闪烁法术能够回复魔力，需要该闪烁法术至少破坏一个之前未曾破坏的符文。而无论破坏多少个符文，回复的魔力值都将是 $b_i$。

那么科尔沃想知道，该如何安排闪烁法术的施展顺序，可以使得在施展完 $m$ 次闪烁法术后，回复的魔力值总和最大呢？

输入格式

第一行包含两个正整数 $n$、$m$，分别表示符文的数量和闪烁法术的数量。

接下来 $m$ 行，每两行包含三个正整数 $b_i$、$l_i$ 和 $r_i$，表示闪烁法术 $i$ 能够回复的魔力值以及破坏符文的编号范围。

输出格式

一个整数，表示最大的闪烁法术的回复魔力值总和。

样例 #1

样例输入 #1

2 2
100 1 2
100 1 1

样例输出 #1

200

样例输入 #2

50 10
204414 14 34
109985 23 25
361742 13 31
324259 16 42
489157 9 41
12122 11 47
871391 23 25
456678 15 47
746949 15 19
266344 13 45

样例输出 #2

3733056

提示

样例解释

如果先施展闪烁法术 $1$，闪烁法术 $2$ 就无法破坏任何新符文了。

如果先施展闪烁法术 $2$，闪烁法术 $1$ 仍然破坏掉之前未曾破坏的 2 号符文。

因此，后者能够回复的总魔力值最大。

数据范围

对于前 $10\%$ 的数据，保证 $1 ≤ m ≤ 10$。

对于前 $30\%$ 的数据，保证 $1\leq n\leq 50, 1\leq m\leq 20$。

对于前 $70\%$ 的数据，保证 $1\leq n\leq 200,1\leq m\leq 3\times 10^3$。

对于 $100\%$ 的数据，保证 $1 ≤ n ≤ 300$，$1 ≤ m ≤ \frac{n \times (n-1)}{2}$，$1 ≤ l_i, r_i ≤ n$，$1 ≤ w_i ≤ 10^6$。