Minimum Obstacles Overcome

There is a number line with m points labeled from 1 to m. Initially at time \(1\), point 1 is occupied by Little Z. At the very beginning, every point on the line has an obstacle.

During each time moment from \(1\) to \(n\), if Little Z is at point \(i\), he may choose an integer \(d \ge 0\) and move to point \(i+d\). In doing so, he "jumps over" every obstacle located at the points in the interval \([i, i+d]\). In other words, in that time moment the cost incurred is the sum of obstacles present on every point from \(i\) to \(i+d\). Normally every point has an obstacle (which counts as \(1\) each), but changes may occur that temporarily remove obstacles.

There are \(k\) changes. The \(i\)th change is described by two integers \(t_i\) and \(x_i\) and means that at time \(t_i\) the obstacle at point \(x_i\) is removed (i.e. its cost becomes \(0\)). This change is only effective during time \(t_i\). It is guaranteed that the changes are given in non‐increasing order of \(t\) (i.e. \(t_1 \ge t_2 \ge \cdots \ge t_k\)).

Little Z will make exactly \(n\) moves, one per time moment, and at the end of time \(n\) he must be exactly at point \(m\). For each \(1 \le i \le k\), considering only the first \(i\) changes (and without the later ones), determine the minimum total number of obstacles that Little Z has to jump over along some valid journey from point 1 at time 1 to point \(m\) at time \(n\).

Note: Even if \(d=0\) (i.e. not moving), the obstacle at the current point will be considered as "jumped over" during that move.

---

Mathematical Formulation:

Let \(obs(t, p)\) be defined as:

[ obs(t, p) = \begin{cases}0, & \text{if there is an event at time } t \text{ with } x=p;\1, & \text{otherwise.} \end{cases} ]

The cost for moving at time \(t\) from point \(i\) to \(j\) (with \(j \ge i\)) is:

[ C(t, i, j) = \sum_{p=i}^{j} obs(t, p). ]

Define \(dp[t][j]\) as the minimum total cost to reach point \(j\) after \(t\) moves. The recurrence is:

[ dp[t][j] = \min_{1 \le i \le j} { dp[t-1][i] + C(t, i, j) }, \quad \text{for } 1 \le t \le n, ; 1 \le j \le m, ]

with initial condition \(dp[0][1] = 0\) (and \(dp[0][j] = +\infty\) for \(j \neq 1\)). The answer for a given set of active changes is \(dp[n][m]\).

inputFormat

The first line contains three integers \(m\), \(n\), and \(k\) (\(1 \le m, n \le 100\) for example, and \(k \ge 1\)).

Then follow \(k\) lines. The \(i\)th of these lines contains two integers \(t_i\) and \(x_i\) indicating that at time \(t_i\) the obstacle at point \(x_i\) is removed. It is guaranteed that \(t_1 \ge t_2 \ge \cdots \ge t_k\).

outputFormat

Output \(k\) lines. The \(i\)th line should contain a single integer: the minimum total number of obstacles jumped over when only the first \(i\) changes occur, under the condition that after time \(n\), Little Z is at point \(m\).

sample

5 3 2
3 3
2 2

6
5

</p>