問題文

N 本の竹があり、1 から N までの番号がつけられています。 時刻 0 において、すべての竹の高さは 0 です。 それぞれの竹は、時刻が 1 経過するごとに高さが 1 増えます。

ナオさんが竹を伐採するイベントが M 回予定されています。 i 番目のイベントは時刻 T_i に行われ、このイベントでは番号が L_i 以上 R_i 以下の竹をすべて伐採します。 ナオさんが高さ x の竹を伐採するとき、彼女は x 点を得ます。 また、伐採された竹は高さが 0 になりますが、その竹はこれ以降も伸び続けます。

M 回のイベントでナオさんが得る得点の総和を求めてください。

制約

• 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
• 入力される値はすべて整数である。

入力例 1

4 2
2 1 2
5 2 3

出力例 1

12

1 番目のイベントが行われる時刻 2 では、竹の高さはそれぞれ 2,2,2,2 です。 竹 1 と 2 を伐採すると、竹の高さはそれぞれ 0,0,2,2 になります。

2 番目のイベントが行われる時刻 5 では、竹の高さはそれぞれ 3,3,5,5 です。 竹 2 と 3 を伐採すると、竹の高さはそれぞれ 3,0,0,5 になります。

2 回のイベントで伐採した竹の高さはそれぞれ 2,2,3,5 なので、その総和である 12 が答えです。

入力例 2

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

出力例 2

113

入力例 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

出力例 3

8003096514