Login Register

Problem E: 架子

Time Limit: 1 Sec Memory Limit: 128 MB
Submit Solution

Description

仓库里有一个C列(column)R行(row)的放物品的架子。

为了能拿到任意格子里的物品，必须使用一个梯子。每次梯子只能靠在一列上，这时可以拿这列和它相邻的两列的物品，但只能拿你爬到的高度以下的所有格子中物品（包括爬到的高度）。

现在你知道今天将要拿的一些物品的位置（行、列），但为了减少危险，想尽可能少爬梯子，即爬梯子的总高度和最小。

编程求出完成今天任务后，所需爬梯子的最小可能的高度和。

Input

输入文件第一行有两个被空格分隔的整数C 和 R, 1 <= C <=100, 1 <= R <=100，分别表示列数和行数。

输入文件第二行只有一个整数N, 1 <= N <= 100，需要拿的物品的数量。

接下面的N行，每行有2个整数A和B，1 <= A <=C, 1 <= B <= R，表示你拿物品的位置。

Output

输出文件只一行，你拿到所有物品后的可能最少爬梯子的高度和。

Sample Input

输入样例1：
5 5
3
2 3
3 4
4 4

输入样例2：
6 20
4
5 6
1 1
6 1
3 7

输入样例3：
10 10
5
9 1
7 6
5 8
4 1
3 2

Sample Output

输出样例1：
4
输出样例2：
9
输出样例3：
11