还不会游泳的 Rut 想要过河。幸运的是，河的某一部分正在建造一座桥，该部分可以表示为一个 $N \times M$ 的网格。每小时，会在之前被水覆盖的一个网格上建造一个桥梁段。例如，五个小时后将建造五个桥梁段。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 需要等待的最少小时数，以便桥梁足够完整，使她能够走到对岸。否则，输出 “nej”。

样例

输入样例 1

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

输出样例 1

7

子任务