Background

The full score for this problem is $50$.

Problem Description

To master the skill of using scissors, Fran came up with a new training method.

He has a paper strip of length $n$ centimeters and a pair of scissors, and he asks Lana to give him cutting instructions.

Lana will give Fran a total of $k$ instructions, each of the form: “Cut the $x$-th strip at a point $l$ centimeters from the left end.”

At the beginning, Fran has only one strip. After the first cut, it becomes two pieces with lengths $l$ and $n-l$. After that, each time he cuts one piece, the two newly created pieces replace the original piece and stay in the same position in the sequence.

More formally: suppose there are currently $m$ strips with lengths $a_1,a_2,\dots,a_m$ in order. If Lana tells him to cut the $x$-th strip at $l$ centimeters, then the new sequence becomes: $a_1,a_2,\dots,a_{x-1},\,l,\,a_x-l,\,a_{x+1},\dots,a_m$.

After all cuts are done, they want to verify whether the process was correct. One way is to count how many different strip lengths appear in the final sequence. Please compute this number.

Input Format

The first line contains two natural numbers $n,k$ ($2 \le n \le 500$，$1 \le k < n$), representing the original strip length and the number of instructions.

The next $k$ lines each contain two natural numbers $x_i,l_i$ ($1 \le x_i \le i$, and $1 \le l_i \le L-1$, where $L$ is the length of the $x_i$-th strip at that time), meaning to cut the $x_i$-th strip from left to right at $l_i$ centimeters from its left end.

Output Format

Output one line with an integer, representing how many different lengths of strips remain after all cuts are completed.

5 1
1 2

2

6 2
1 4
1 2

1

10 3
1 2
2 3
3 2

2

Hint

Sample Explanation

Explanation for Sample #1: $[5] \to [2,3]$.

Explanation for Sample #2: $[6] \to [4,2] \to [2,2,2]$.

Explanation for Sample #3: $[10] \to [2,8] \to [2,3,5] \to [2,3,2,3]$.

Subtasks

Translated by ChatGPT 5