問題文

$2$ 次元平面があり、あなたは今いる座標 $(0, 0)$ から目的地の座標 $(N, N)$ に移動したいです。
あなたがマス $(r, c)$ にいるとき、あなたは次の $2$ 種類の移動を行うことができます。

• 基本的に $1$ 円払い、マス $(r, c)$ からマス $(r+1, c)$ へ移動する。この移動は $r < N$ のとき使える。
• 基本的に $1$ 円払い、マス $(r, c)$ からマス $(r, c+1)$ へ移動する。この移動は $c < N$ のとき使える。

しかし、次の $M$ 個の移動だけは無料で行うことができます。（逆に、$1$ 円払っての移動はできないことに注意してください。）

• $t_i = 1$ のとき：マス $(x_i, y_i)$ からマス $(x_i + 1, y_i)$ への移動が無料で行える。
• $t_i = 2$ のとき：マス $(x_i, y_i)$ からマス $(x_i, y_i + 1)$ への移動が無料で行える。

入力

$N$ $M$
$t_1$ $x_1$ $y_1$
$t_2$ $x_2$ $y_2$
$t_3$ $x_3$ $y_3$
 $\vdots$
$t_M$ $x_M$ $y_M$

出力

答えを出力してください。

制約

• $1 \leq N \leq 200000$
• $0 \leq M \leq 200000$
• $1 \leq t_i \leq 2$
• $t_i = 1$ のとき $0 \leq x_i < N$ かつ $0 \leq y_i \leq N$
• $t_i = 2$ のとき $0 \leq x_i \leq N$ かつ $0 \leq y_i < N$
• $(t_1, x_1, y_1), (t_2, x_2, y_2), (t_3, x_3, y_3), \dots, (t_N, x_N, y_N)$ は相異なる
• 入力はすべて整数

サンプル

サンプル1

入力

2 1
1 0 0

出力

21

下図の通り、移動方法は $6$ つあります。金額の総和は $3 + 3 + 3 + 4 + 4 + 4 = 21$ 円です。

5 0

2520

400 10
2 73 190
2 351 261
1 164 365
1 62 221
1 18 209
1 358 211
2 32 206
1 147 46
1 36 77
2 5 203

85571926