Problem Description

There are $ N $ bamboos numbered from $ 1 $ to $ N $. At time $ 0 $, the height of all bamboos is $ 0 $. Each bamboo grows $ 1 $ unit in height every time unit.

There are $ M $ scheduled events where Nao will cut the bamboos. The $ i $-th event occurs at time $ T_i $ and cuts all bamboos with numbers from $ L_i $ to $ R_i $ inclusive. When Nao cuts a bamboo of height $ x $, she gains $ x $ points. The cut bamboos will have their height reset to $ 0 $, but they will continue to grow afterwards.

Calculate the total score Nao will gain from the $ M $ events.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ T_1 $ $ L_1 $ $ R_1 $ $ T_2 $ $ L_2 $ $ R_2 $ $\vdots$ $ T_M $ $ L_M $ $ R_M $

Output Format

Output the total score Nao will gain from the $ M $ events.

Sample Input and Output

Sample Input #1

4 2
2 1 2
5 2 3

Sample Output #1

12

Sample Input #2

10 5
8 1 4
11 6 7
20 1 1
31 9 9
36 1 1

Sample Output #2

113

Sample Input #3

10 10
76724435 3 4
118633459 1 2
288866156 6 9
470883673 6 10
521545097 2 4
827053186 1 1
856004743 2 4
873331881 1 1
909855542 6 10
916091889 8 9

Sample Output #3

8003096514

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq T_1 < T_2 < \cdots < T_M \leq 10^9$
• $1 \leq L_i \leq R_i \leq N$
• All input values are integers.

Sample Explanation 1

At time $ 2 $ when the first event occurs, the heights of the bamboos are $ 2, 2, 2, 2 $. Cutting bamboos $ 1 $ and $ 2 $ results in heights $ 0, 0, 2, 2 $. At time $ 5 $ when the second event occurs, the heights are $ 3, 3, 5, 5 $. Cutting bamboos $ 2 $ and $ 3 $ results in heights $ 3, 0, 0, 5 $. The heights of the cut bamboos are $ 2, 2, 3, 5 $, so the total sum of $ 12 $ is the answer.

见题面 Input 部分

见题面 Output 部分