每个测试点时限 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行,每行两个整数ai,bi,表示乘客i想坐车的起点站和终点站,数据满足1<=ai<bi<=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 共三块钱

来源

火车

备注

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