背景

题目描述

曲水流觞，但是有四个瓜批丢了 $m$ 条叶子船进去看哪个跑得远。

具体地，第 $i$ 条叶子船会在 $[l_i,r_i]$ 的时间段内在中间的北海停留，并且有 $a_i$ 的击沉价值。

对于小基来说，他希望击沉寄存的船，所以一些船的击沉价值 $a_i$ 为正；他不希望击沉佚名的船，所以一些船的击沉价值 $a_i$ 为负；小基是成都人，所以 $a_i$ 也可能为 $0$ 。

作战总共持续 $n$ 个时刻，小基在每个时刻都可以选择是否丢皮孩进去，皮孩会不分敌我地击沉当前所有停留在北海的叶子船，保证皮孩数量充足。

小基希望击沉的总价值尽量高，请你帮他求出这个值。

输入

第一行有两个整数 $n,m\ (1\le n,m \le 2\times10^5)$，分别表示总共的时刻数和叶子船的数量。

接下来的 $m$ 行每行有三个整数 $l_i,r_i,a_i\ (1\le l_i \le r_i \le n,|a_i|\le 10^9)$ ，表示第 $i$ 条叶子船停留的时间段和它的击沉价值。

输出

输出一行一个整数，表示最大的总击沉价值。

样例

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

90

一种方案：时刻 $1$ 丢皮孩，时刻 $2,3$ 不丢皮孩，第 $1,2$ 条叶子船会被击沉。

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

一种方案：在时刻 $1,3$ 丢皮孩，其余时刻不丢皮孩，第 $2,3,4,5,7$ 条叶子船会被击沉。

来源

2025 UESTC ICPC Training for Dynamic Programming and Search