问题描述

伊织酱的新兴爱好是金字塔。

伊织酱打算将 $1$ 边长为 $L$ 的球状石头按照正四面体的形式排列，制作成类似金字塔的结构。为了能够稳定地放在桌子上，她打算将石头排列在一个木板上，木板上有 $L \times (L+1) / 2$ 个环形孔。然而，她在开孔时失败了，导致无法在一些孔上放置石头。按照和正四面体状排列石头相同的方式继续排列石头，伊织酱能够放置多少块石头呢？按照“按照和正四面体状排列石头相同的方式继续排列石头”指的是以下排列方式：

• 在正四面体状排列石头时，我们称将石头放置在下标为 $(i,j,k)$ 的位置上，其中 $i (1 \leq i \leq L)$ 表示从下往上数的第 $i$ 层，$j (1 \leq j \leq L-i+1)$ 表示从后往前数的第 $j$ 列，$k (1 \leq k \leq j)$ 表示从左往右数的第 $k$ 个石头。注意，在从下往上数的第 $1$ 层的后面从后往前数的第 $x (1 \leq x \leq L)$ 列将放置 $x$ 个石头。
• 首先，将所有位于从下往上数的第 $1$ 层的能够放石头的位置都放置石头。
• 接下来，按照正四面体状排列石头时的规则，在从下往上数的第 $2$ 层到第 $L$ 层的位置 $(i,j,k)$ 中，只要位置 $(i-1,j,k)$、位置 $(i-1,j+1,k)$ 和位置 $(i-1,j+1,k+1)$ 上都有石头，就在当前位置放置石头，直到没有可以放置石头的位置为止。

输入

输入以以下格式从标准输入中给出：

$L$ $N$ $A_1$ $B_1$ $A_2$ $B_2$ ： $A_N$ $B_N$

• 第 $1$ 行包含两个整数 $L (2 \leq L \leq 10^5)$ 和 $N (0 \leq N \leq \min(10^5, L \times (L+1) / 2))$，以空格分隔。表示计划将石头按正四面体的规则排列，同时有 $N$ 个位置无法放置石头。
• 第 $2$ 行到第 $N+1$ 行，每行包含两个整数 $A_i (1 \leq A_i \leq L)$ 和 $B_i (1 \leq B_i \leq A_i)$，以空格分隔。表示无法在第 $A_i$ 列的第 $B_i$ 个位置放置石头。保证同一位置信息不会重复给出。

子任务

本问题共设有若干个子任务，满足以下要求的数据集将给出部分分：

• 当 $N \leq 20$，即数据集 $1$ 时，能够正确解决该子任务将获得 $58$ 分。
• 当对所有测试用例都能正确回答时，将获得满分。

输出

输出一个整数，表示伊织酱能够放置的石头数量。末尾输出换行符。

输入样例1

3 1
2 1

输出样例1

6

伊织酱可以将石头放置在位置 $(1,1,1)$、$(1,2,2)$、$(1,3,1)$、$(1,3,2)$、$(1,3,3)$ 和 $(2,2,2)$ 共 $6$ 处。

输入样例2

100000 0

输出样例2

166671666700000

注意到，这里并没有因为开孔失败而无法放置石头。

输入样例3

6 4
3 2
6 6
5 2
3 3

输出样例3

25