Description

考虑由 0 和 1 组成的长度为 $N$ 的字符串。该字符串的分数计算如下：

• 对于每个计分区间 $i(1≤i≤M)$ ，如果字符串在 $l_i$ 到 $r_i$ 之间至少包含一个 1​，那么总分数将会加上 $a_i$。

计算字符串的最大可能分数。

Input

输入格式如下：

$N\ M\\l_1​\ r_1​\ a_1\\​l_2\ ​r_2\ ​a_2\\​:\\l_M\ ​r_M\ ​a_M​$​

输入中的所有值都是整数。

$1≤N≤2×10^5\\1≤M≤2×10^5\\1≤l_i​≤r_i​≤N\\∣a_i​∣≤10^9$。

Output

输出字符串的最大可能分数。

Samples

5 3
1 3 10
2 4 -10
3 5 10

20

10001 的分数是 $a_1​+a_3​=10+10=20$。

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

90

100 的分数为 $a_1​+a_2​=100+(−10)=90$。

1 1
1 1 -10

0

0 的分数为0。

1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

5000000000

答案可能超出32位整数。

6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7

10

例如，101000 的得分为 $a_2​+a_3​+a_4​+a_5​+a_7​=10+(−8)+5+9+(−6)=10$。