该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一条河从东向西流过,并把魔法世界分为南北两个部分。河的两岸各有 $\red{n}$个城市,且北岸的每一个城市都与南岸的某个城市是友好城市，而且对应的关系 是一一对应的,如图所示。

现在要求在两个友好城市之间建立一条航线,但为了安全起见，所有航线都不 能相交,因此,不是所有的友好城市都能建立航线。请问,最多能建多少航线?

输入格式

第一行两个由空格分隔的整数$\red{x,y,10≤}$$\red{x≤}$$\red{6 000,10≤}$$\red{y≤}$$\red{100}$。$\red{x}$表示河的 长度而$\red{y}$表示宽,第二行是一个整数$\red{n(1≤}$$\red{n≤}$$\red{5 000),}$表示分布在河两岸的城市对 数。接下来的$\red{n}$行每行有两个由空格分隔的正数$\red{c,d(c,d≤}$$\red{x),}$描述每一对友好 城市与河起点的距离,$\red{c}$表示北岸城市的距离,而$\red{d}$表示南岸城市的距离。在河的 同一边,任何两个城市的位置都是不同的。

输出格式

在安全条件下能够开通的最大航线数目。

样例

输入样例

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

输出样例

3