问题描述

具体描述见教材p267： 今仓库里有一个 C 列(column) R 行(row)的放物品的架子。为了能拿到任意格子里的物必须使用一个梯子。每次梯子只能靠在一列上，这时可以拿这列和它相邻的两列的物品，但只能拿你爬到的高度以下的所有格子中的物品(包括爬到的高度)。现在你知道今天将要拿的一些物品的位置(行、列)，但为了减少危险，想尽可能少爬梯子，即爬梯子的总高度和最小。编程求出完成今天任务后，所需爬梯子的最小可能的高度和。

格式

输入

第1行有两个被空格分隔的整数 C 和 R , 1≤C≤100, 1≤R≤100，分别表示列数和 行数; 第2行只有一个整数 n, 1≤n≤100，表示需要拿的物品的数量； 接下来的 n 行，每行有 2 个整数 A 和 B, 1≤A≤C, 1≤B≤R，表示你拿物品的位置。

输出

仅1行，你拿到所有物品后的可能最少爬梯子的高度和。

样例

5 5
3
2 3
3 4
4 4

4

6 20
4
5 6
1 1
6 1
3 7

9

10 10
5
9 1
7 6
5 8
4 1
3 2

11

限制

1s, 64MB.