题目背景

1s, 2G, brobygge2

题目描述

不会游泳的 Rut 想要穿过一条河。幸运的是，河流的一段正在修建桥梁，这一段可以表示为一张 $N \times M$ 的网格。每经过 1 小时，就会在一块原本被水覆盖的格子上建成一段桥面。例如，经过 5 小时将建成 5 段桥面。Rut 已经拿到了最先建成的桥面位置列表。她知道：当她能够在不需要游泳的情况下，沿着桥从河的一侧走到另一侧时，就可以过河。她从第 $0$ 行出发，目标是到达第 $N - 1$ 行。这两行上各有一整条可供沿河行走的陆地。她可以在不被水覆盖的格子之间，上下、下上、左右移动。现在她想知道：给定的这些桥段是否足以让她过河；如果可以，她最少需要等待多少小时，才能在桥面足够完成时到达对岸。

图 1：样例 $1$ 在 $4$ 小时和 $7$ 小时后的示意图。只有在 $7$ 小时后才会出现通往对岸的路径。

输入格式

输入的第一行包含三个整数 $N, M$（$3 \le N, M \le 10^9$）和 $T$（$1 \le T \le 10^5$），分别表示网格的行数、列数以及将要建成的桥段数。

接下来有 $T$ 行，其中第 $i$ 行包含两个整数 $R$（$1 \le R \le N - 2$）和 $C$（$0 \le C \le M - 1$），表示第 $i$ 小时完成的格子的行与列。注意：本题中，第 $0$ 行是底部行。

输出格式

如果 Rut 能过河，输出一个整数：Rut 至少需要等待的小时数，使得桥面足以通往对岸；否则，输出 $\texttt{nej}$（瑞典语「No」）。

7 3 8
2 1
1 0
4 1
5 1
2 0
3 0
4 0
3 1

7

提示

子任务

本题采用捆绑测试。