题目描述

小蓝与小红在玩一个游戏，这个游戏在一个$N\times M$的地图上进行。地图上的点范围从$(1,1)$一直到$(N,M)$。地图上还有$K$个位置不同的武士，每名武士都在相应的二维地图坐标上。起初在$(1,1)$处放置了一名忍者。在$(1,1)$处一定没有武士。
小蓝和小红轮流操作这名忍者。每次操作忍者都可以从以下两个操作中选取。

1. 移动忍者，如果是小蓝，则只能向下移动也就是只能从$(x,y)$移动到$(x+1,y)$，如果是小红则只能向右移动也就是只能从$(x,y)$移动到$(x,y+1)$。如果目标单元格不存在或被武士占据，则无法进行此操作。
2. 不移动忍者。

如果忍者连续两次没有被移动，则游戏结束。

小蓝希望在对局结束前尽可能多地采取行动(包括不移动忍者)，而小红则希望在对局结束前尽可能少地采取行动。小蓝最终会移动多少次忍者？

输入格式

第一行三个正整数$N,M,K$，代表地图的大小，以及武士的数量。
接下来$K$行每行两个正整数$x_i,y_i$代表武士的坐标。

输出格式

一行一个正整数$ans$，小蓝最终会移动多少次忍者？

输入输出样例

3 3 1
3 2

2

样例解释

小蓝向下移动忍者，忍者坐标：$(1,1)->(2,1)$。
小红向右移动忍者，忍者坐标：$(2,1)->(2,2)$。
小蓝不移动忍者。
小红不移动忍者。

数据范围

• $1 \leq N,M \leq 2\times 10^5$
• $0 \leq K \leq 2\times 10^5$
• $1 \leq x_i \leq N$
• $1 \leq y_i \leq M$
• If $i \neq j$, $(x_i,y_i) \neq (x_j,y_j)$
• $(x_i,y_i) \neq (1,1)$
• $x_i$和$y_i$都是整数.