身无彩凤双飞翼
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个�行�列的网格图，小红初始在左上角 (1,1)，最终要去到右下角 (�,�) 去见小蓝 ，每一步只能向右或者向下走。

网格图上有 � 个障碍物，有障碍物的地方不能通过。

邪恶的小念不希望小红见到小蓝，他想知道，他最少要把几个非障碍物点变成障碍物点，才能阻止他们相见（起点和终点不能改变）。


输入描述:

第一行三个整数 n,m,k(1\leq n,m\leq 1000,1\leq k\leq n*m-2)。，分别表示网格图的行数，网格图的列数，网格图的初始障碍数

接下来 k 行，每行两个整数 a_i,b_i，表示在点(a_i,b_i)有一个障碍物。

输出描述:

输出一个非负整数，表示最少要改变几个格子状态，才能阻止小红与小蓝相见
示例1

输入

复制 
5 3 5
1 2
1 3
2 2
2 3
3 2

输出

复制 
1

说明

堵住 (4,1) 就可以了

1\leq n,m\leq 1000。

1\leq k\leq n*m-2。

保证 (a_i,b_i) 在格点范围内，且不包含起点和终点。