釘(Nails)

JOI くんは板に釘を刺して遊んでいる．下図のように，JOI くんは一辺N 本の正三角形の形に釘を並べて刺した．上からa 行目(1 ≤ a ≤ N) にはa 本の釘が並んでいる．そのうち左からb 本目(1 ≤ b ≤ a) の釘を(a, b) で表す．

図1: 釘の並び方（N = 5 の場合）

釘を頂点とする正三角形が，「各辺が全体の正三角形の辺のいずれかと平行で，全体の正三角形と同じ向き」であるとき，この正三角形を「よい正三角形」と呼ぶ．すなわち，「よい正三角形」とは，3 本の釘(a, b), (a + x, b), (a + x, b + x) を頂点とする正三角形のことである（ただしa, b, x は1 ≤ a < N, 1 ≤ b ≤ a, 1 ≤ x ≤ N - a) をみたす）．

JOI くんは，輪ゴムを使って，「よい正三角形」の周りを囲うことにした．

図2: 輪ゴムによる「よい正三角形」の囲い方の例

課題

正三角形の一辺に並んでいる釘の本数N と，JOI くんが持っている輪ゴムの数M と，M 本の輪ゴムによる「よい正三角形」の囲い方が与えられたとき，1 本以上の輪ゴムで囲われた釘の本数を求めるプログラムを作成せよ．

制限

2 ≤ N ≤ 5000     一辺に並んでいる釘の本数
1 ≤ M ≤ 500000 (= 5 × 10⁵)     輪ゴムの数

入力

標準入力から以下のデータを読み込め．

• 1 行目には整数N, M が空白を区切りとして書かれている．N は正三角形の一辺に並んでいる釘の本数を，M はJOI くんの持っている輪ゴムの数をそれぞれ表す．
• 続くM 行は輪ゴムによる「よい正三角形」の囲い方の情報を表す．i + 1 行目(1 ≤ i ≤ M) には整数A_i, B_i, X_i (1 ≤ A_i < N, 1 ≤ B_i ≤ A_i, 1 ≤ X_i ≤ N - A_i) が空白を区切りとして書かれている．これは，i本目の輪ゴムは3 本の釘(A_i, B_i), (A_i + X_i, B_i), (A_i + X_i, B_i + X_i) を頂点とする「よい正三角形」を囲っていることを表す．

出力

標準出力に，1 本以上の輪ゴムに囲われている釘の本数を1 行で出力せよ．

採点基準

採点用データのうち，配点の30% 分については，M ≤ 10000 を満たす．

入出力例

入力例 1

5 2
2 2 1
2 1 3

出力例 1

12

この例は図2 のような「よい正三角形」の囲い方に対応している．この例において，(1, 1), (4, 4), (5, 5) 以外の12 本の釘が1 本以上の輪ゴムで囲われている．

---