Problem Description

Iori's latest obsession is pyramids.

Iori plans to arrange $L \times (L+1) \times (L+2) / 6$ spherical stones with a radius of $ 1 $ into a regular tetrahedron shape with $ L $ stones on each side, creating something like a pyramid. To ensure stability, she intends to place them on a wooden board with $L \times (L+1) / 2$ circular holes. However, she made mistakes while drilling the holes, rendering some of them unusable for placing stones. How many stones can Iori place in the same manner as arranging them in a regular tetrahedron? The term "same manner as arranging them in a regular tetrahedron" refers to the following placement method:

• When arranging stones in a regular tetrahedron, the position where the stone should be placed at the $ i $th level from the bottom ( $1 \leq i \leq L$ ), the $ j $th column from the back ( $1 \leq j \leq L-i+1$ ), and the $ k $th stone from the left ( $1 \leq k \leq j$ ) is called position $ (i,j,k) $. It is assumed that the $ x $th column from the back at the bottom level ( $1 \leq x \leq L$ ) contains $ x $ stones.
• First, place stones in all positions at the bottom level where the holes were successfully drilled and are usable.
• Then, for positions $ (i,j,k) $ from the second level to the $ L $th level, place stones in positions where there are stones at positions $ (i-1,j,k) $, $ (i-1,j+1,k) $, and $ (i-1,j+1,k+1) $, repeating this operation until there are no more positions where stones can be placed.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains two integers $ L $ ( $2 \leq L \leq 10^5$ ) and $ N $ ( $0 \leq N \leq \min(10^5, L \times (L+1) / 2)$ ), separated by a space. This indicates the planned arrangement of stones in a regular tetrahedron with $ L $ stones on each side and $ N $ positions where the holes were drilled unsuccessfully.
• The next $ N $ lines provide information about the unsuccessfully drilled positions. The $ i $th line ( $1 \leq i \leq N$ ) contains two integers $ A_i $ ( $1 \leq A_i \leq L$ ) and $ B_i $ ( $1 \leq B_i \leq A_i$ ). This indicates that the hole at the $ A_i $th column from the back and the $ B_i $th stone from the left was unsuccessfully drilled. It is guaranteed that no position information is given more than once.

Output Format

Output the number of stones Iori can place in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 1
2 1

Sample Output #1

6

Sample Input #2

100000 0

Sample Output #2

166671666700000

Sample Input #3

6 4
3 2
6 6
5 2
3 3

Sample Output #3

25

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve dataset 1 where $N \leq 20$, you will be awarded 58 points.
• If you correctly solve all test cases, you will be awarded the full points.

Sample Explanation 1

Stones can be placed at positions $ (1,1,1) $, $ (1,2,2) $, $ (1,3,1) $, $ (1,3,2) $, $ (1,3,3) $, and $ (2,2,2) $, totaling 6 positions.

Sample Explanation 2

Be aware that there might be cases where no holes were actually drilled unsuccessfully.

见题面 Input 部分

见题面 Output 部分