Monocarp 玩电脑游戏。游戏中有 $$$n$$$ 不同的盔甲套装和 $$$m$$$ 不同的武器。如果角色装备第 $$$i$$$ 套盔甲并使用第 $$$j$$$ 武器,则其力量通常等于 $$$i + j$$$;但盔甲和武器的某些组合可以很好地协同作用。形式上,存在一个 $$$q$$$ 有序对的列表,如果 $$$(i, j)$$$ 属于此列表,则装备第 $$$i$$$ 套盔甲并挥舞第 $$$j$$$ 武器的角色的力量不是 $$$i + j$$$,而是 $$$i + j + 1$$$。
最初,Monocarp 的角色只有 $$$1$$$-st 盔甲套装和 $$$1$$$-st 武器。 Monocarp可以在一小时内获得一件新武器或一套新盔甲。如果他想获得第 $$$k$$$ 盔甲套装或第 $$$k$$$ 武器,他必须拥有一套盔甲套装和一件武器的组合,使他的力量达到 $$$k$$$ 或更高。当然,在 Monocarp 获得武器或盔甲套装后,他可以用它来获得新的盔甲套装或武器,但他也可以使用任何旧的盔甲套装和/或武器。
Monocarp想要获得第$$$n$$$盔甲套装和第$$$m$$$武器。他至少需要花多少小时来完成这项工作?
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — 分别是装甲组数和武器数。
第二行包含一个整数 $$$q$$$ ($$$0 \le q \le \min(2 \cdot 10^5, nm)$$$) — 协同作用良好的组合数量。
然后是 $$$q$$$ 行,第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i \le n$$$; $$$1 \le b_i \le m$$$) 意味着第 $$$a_i$$$ 装甲组与第 $$$b_i$$$ 个武器。所有对 $$$(a_i, b_i)$$$ 都是不同的。
输出
打印一个整数 - Monocarp 获得第 $$$n$$$ 盔甲套装和第 $$$m$$$ 武器所需的最少小时数。
示例
输入 #1
3 4 0
输出 #1
3
输入 #2
3 4 2 1 1 1 3
输出 #2
2
注意
第一个例子中,Monocarp可以获得最强的护甲套装和最强的武器,如下:
1.使用$$$1$$$-st盔甲套装和$$$1$$$-st武器获得$$$2$$$-nd武器;
2.使用$$$1$$$-st盔甲套装和$$$2$$$-nd武器获得$$$3$$$-rd盔甲套装;
3. 使用$$$3$$$-rd 盔甲套装和$$$2$$$-nd 武器获得第$$$4$$$-th 武器。
在第二个例子中,Monocarp可以获得最强的护甲套装和最强的武器,如下:
1.使用$$$1$$$-st盔甲套装和$$$1$$$-st武器获得$$$3$$$-rd盔甲套装(它们协同作用很好,所以Monocarp的力量不是$$$2$$$而是$$$3$$$);
2. 使用$$$3$$$-rd 盔甲套装和$$$1$$$-st 武器获得$$$4$$$-th 武器。