配点: 100 点
JOI君正在板上玩钉子。如下图所示,JOI君将指甲插成每边有N个长度的等边三角形。从上面 a 行目 (1\leqq a\leqq N)是 a 书钉排列整齐。从左边开始 b 本目 (1\leqq b\leqq a)指甲 (a, b) 代表。

如果一个以钉子为顶点的等边三角形“每一条边都与整个等边三角形的一条边平行,且方向与整个等边三角形相同”,那么这个等边三角形就可以称为“好等边三角形”。换句话说,“好的等边三角形”是3 书钉 (a, b), (a + x, b), (a + x, b + x) 是一个等边三角形,其顶点是 a, b, x 是 1 \leqq a < N, 1 \leqq b \leqq a, 1 \leqq x \leqq N − a )。
JOI君决定用橡皮筋围成一个“好的等边三角形”。

課題
等边三角形一侧排列的钉子数量 N 以及JOI君拥有的橡皮筋的数量。 M 和M 给出如何用橡皮筋围成一个“好的等边三角形”,1 编写一个程序来查找被多个橡皮筋包围的钉子的数量。
制限
| 2 \leqq N \leqq 5000 | 一侧排列的钉子数量 |
| 1 \leqq M \leqq 500000 \,(= 5\times 10^5) | 橡皮筋数量 |
入力
从标准输入读取以下数据。
- 1 行是一个整数 N, M 以空格作为分隔符。N 是等边三角形一侧排列的钉子数量,M 代表JOI君拥有的橡皮筋的数量。
- 继续 M 线表示有关如何用橡皮筋围成“良好的等边三角形”的信息。i + 1 行目 (1 \leqq i \leqq M) 是一个整数 A_i,B_i,X_i (1\leqq A_i < N, 1\leqq B_i\leqq A_i , 1\leqq X_i \leqq 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\leqq 10000 满意。
入力例 1
5 2 2 2 1 2 1 3
出力例 1
12
该示例显示在 它支持封闭“好的等边三角形”,例如 2 。在这个例子中,(1, 1), (4, 4), (5, 5) 以外 12 书钉 1 被不止一根橡皮筋包围。