레이팅 미적용Wanting to perfect his scissors using skills, Fran came up with a new exercise. He
got himself a paper strip of length \(n\) centimetres and, of course, a pair of scissors.
He also asked Lana to assist him for the exercise.
Lana will give Fran \(k\) instructions of the following type: "Cut the \(x\)-th strip at
\(l\) centimetres". At the beginning, Fran has one strip. After the first action, he
will have two strips: the first strip \(l\) centimetres long, and the second one \(n - l\)
centimetres long (the remainder of the original strip). After that, Fran will cut
either the first or the second strip - depending on Lana’s instruction. Each time he cuts a strip, the two
new pieces replace the original strip in the sequence.
More formally, suppose Fran has \(m\) strips of lengths \(a_{1}\), \(a_{2}\), ..., \(a_{m}\). If Lana tells him to cut the \(x\)-th strip
at \(l\) centimetres, the new sequence of strip lengths becomes: \(a_{1}\), \(a_{2}\), ..., a_{\(x - 1\)}, l, \(a_{x} - l\), a_{\(x+1\)}, ..., \(a_{m}\).
After performing all cuts, he and Lana want to verify the cutting process. One way to do that is to count
how many distinct strip lengths there are at the end. Your task is to compute this number.
The first line contains two natural numbers \(n\) and \(k\) (\(2 \le n \le 500\), \(1 \le k < n\)), the length of the original
strip and the number of instructions Lana gives Fran.
Each of the following \(k\) lines contains two natural numbers \(x_{i}\) and \(l_{i}\) (\(1 \le x_{i} \le i\), \(1 \le l_{i} \le L - 1\), where \(L\)
is the length of the \(x_{i}-th\) strip at that moment). These numbers indicate that Fran should cut the \(x_{i}-th\)
strip at \(l_{i}\) centimetres (counting strips from the beginning).
In the first and only line, write one number - the number of distinct strip lengths that Fran will be left
with after he performs all the cuttings.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 9점 | \(k \le 3\) |
2 | 6점 | \(l_{i} = 1\) for all \(i = 1\), ..., k |
3 | 13점 | \(x_{i} = i\) for all \(i = 1\), ..., k |
4 | 22점 | No additional constraints. |
5 1
1 226 2
1 4
1 2110 3
1 2
2 3
3 22Clarification of the first example:
[5] →[2, 3]
Clarification of the second example:
[6] →[4, 2] →[4, 2] →[2, 2, 2]
Clarification of the third example:
[10] →[2, 8] →[2, 8] →[2, 3, 5] →[2, 3, 5] →[2, 3, 2, 3]