1522 - 航线

通过次数

0

提交次数

55

Time Limit : 1 秒
Memory Limit : 64 MB

某国家被一条河划分为南北两部分,在南岸和北岸总共有n对城市,每对城市在对岸都有唯一的友好城市,任何城市都没有相同的友好城市。每一对友好城市都希望有一条航线来往,于是他们向政府提出了申请。由于河面上终年有雾,政府决定允许开通的航线互不交叉(如果两条航线交叉,将有很大机会撞船)。兴建哪些航线可以在安全条件下有最多航线可以开通。

Input

第1行为2个正整数x和y,表示河的长度和宽度。10≤x≤6000,10≤y≤100。

第2行一个正整数n表示分布在河两岸的城市对数,1≤n≤5000。

接下来的n行,每行两个整数c和d,c、d≤x,描述每一对友好城市与河起点的距离,c表示北岸城市的距离,d表示南岸城市的距离。在河的同一边,任何两个城市的位置都是不同的。

每一行当中的两个数之间用一个空格隔开。

Output

一行一个数,表示在安全条件下能够开通的最大航线数目。

Examples

Input

30 4
5
4 5
2 4
5 2
1 3
3 1

Output

3

Source

课课通