高坚果

题目背景

噜噜特别喜欢玩植物大战僵尸，这回他玩的关卡是奖励关，这一关是用高坚果在地图上翻滚消灭僵尸。

地图上有一些僵尸，噜噜可以在地图上的最左一列放置高坚果。高坚果只会向右上和向右下翻滚两种移动方式。在碰到僵尸时就能消灭僵尸（僵尸不会被多次消灭）。另外高坚果在碰到地图边缘或者消灭僵尸后就会反弹，即切换移动方式，最后高坚果会从地图的最右侧离开地图。

噜噜喜欢积攒多个可放置的高坚果，然后在一瞬间快速的全部放置在地图上。在高坚果运动过程中，僵尸不会移动，即整个过程，僵尸是固定不动的。他想知道，在给定放置的顺序之后，地图上还剩下的僵尸数量。

题目描述

给定一个 $n$ 行 $n$ 列 的地图，其中第一列表示地图的最左一列。地图上有 $m$ 个僵尸，所在地图的 $x$ 行 $y$ 列，保证地图的同一格内没有多个僵尸。

另外噜噜准备放置 $k$ 个高坚果，分别依次放置在最左一列的第 $x$ 行，求最后还剩下多少僵尸。

移动规则

每个高坚果从 最左一列 的指定行出发，初始移动方向为：

• 右上：每次移动到 $(x-1,\;y+1)$
• 右下：每次移动到 $(x+1,\;y+1)$
  并满足：

1. 若高坚果 碰到僵尸所在格，则该僵尸被消灭（同一僵尸不会被多次消灭），并且高坚果 立即反弹（切换“右上/右下”移动方式）。

2. 若高坚果 碰到地图边缘（上边界或下边界），则高坚果 反弹（切换移动方式）。

3. 高坚果最终会从地图的最右侧离开地图（离开后不再影响地图）。

4. 僵尸在整个过程中保持静止。

5. 多个高坚果按输入给定顺序依次放置，前一个消灭的僵尸会影响后续高坚果的运动结果。

输入格式

• 输入第一行包含三个正整数 $n, m, k$，分别表示一个 $n \times n$ 的矩阵、$m$ 个僵尸、$k$ 次操作。
• 接下来 $m$ 行，每行两个正整数 $x, y$，表示在 $x$ 行 $y$ 列有一个僵尸。
• 接下来 $k$ 行，每行两个整数 $x, d$，表示将高坚果放置在第 $x$ 行，初始的移动方式为 $d$：
  • $d = 0$：表示向右上方移动
  • $d = 1$：表示向右下方移动

输出格式

输出一行仅一个数字，即地图最终剩下的僵尸数量。

5 6 2  
3 2  
3 5  
4 4  
1 2  
3 4  
3 3  
2 1  
5 0

2

样例说明

第一个高坚果放置在第 2 行，初始移动方向是右下，运动到 (3,2) 后消灭了僵尸，并且切换移动方向为右上。之后运动到 (1,4) 碰触到地图边缘，切换移动方向为右下。最后在 (2,5) 翻滚出地图。

第二个高坚果放置在第 5 行，初始移动方向是右上，运动到 (3,3) 后消灭了僵尸，并且切换移动方向为右下。接着运动到 (4,4)，切换移动方向为右上。然后运动到 (3,5)，切换移动方向为右下，不过此时已经翻滚出地图。

最终剩余僵尸数量为 2。

数据范围

对于所有测试数据，有：

• $1 \le n \le 2000$
• $1 \le m \le 5\times 10^5$
• $0 < k \le 5\times 10^4$

测试点划分