每个测试点时限 1s 内存限制 192MB

背景

你完成了喵星人的任务，喵星人对你的表现非常满意。但它们遗憾的告诉你：由于使用“快刀”要走100个部门盖400个章，步骤太繁琐，它们决定取消之前的行动……

不过，它们闲不下来，决定对地球进行控制……而控制的第一项，就是铁路系统……

描述

喵星人决定改造铁路的售票系统。

它们希望改造后的售票系统是这样的：现以车次A为例：

A一共有n站（1,2,3,4,...n,包含起点站和终点站），A可以同时承载的乘客为m人。售票开始时，第1站可以卖出m张票，这m张票的到达站可以是第2到第n站中的任意一站。当第a站卖出到达站为k站的1张票时，第a站可以卖出的票数-1，第k站可以卖出的票数+1，同时，第k站卖出票的到达站可以是第k+1到第n站中的任意一站。(k=n时不能卖出票)

由于喵星人手指太少【第一题有提到=。=】，它们决定任何一张票的价格都是1块钱。

现在，有q个人想坐这趟列车，怎样让他们以一个合理的顺序买票使喵星人获得最大收益？这个问题就交给走狗你了。

输入格式

第一行三个正整数n,m,q，含义见描述。

第2行至第q+1行，每行两个整数a_i,b_i,表示乘客i想坐车的起点站和终点站，数据满足1<=a_i<b_i<=n。

输出格式

一个整数，最大收益

样例输入

4 2 4

1 2

1 3

1 4

2 4

样例输出

3

数据范围与约定

对于20%的数据 m<=2

对于40%的数据 m<=10

对于50%的数据 n<=50

对于所有数据 n<=1000,m<=50,q<=100000

这题数据非常弱！不优化都嫩过！业界良心！

样例解释

1 ->2 ,1->3,2->4 共三块钱

来源

火车

备注

我家水表在门外，顺丰请给水表收。