题目描述

小A准备在接下来的m天中锻炼，由于他不能走得太多以至于累死（怎么可能呢），所以他这m天最多一共只能走n步。

这个运动软件为了激励小A走路，推出了k种激励措施，每种激励措施都形如“如果你第p天走完了q步，那么第p天中接下来的每一步都会给你加1积分”。激励措施可以叠加，即走一步你可能可以获得多于1积分。

现在小A想知道，他最多可以获取多少积分呢？

输入格式

第一行三个整数n,m,k，意义如上。

接下来k行，每行两个整数p,q，表示一个激励措施，意义如上。

输出格式

一行1个整数，表示m天后最多可以获得的积分。

输入样例 #1

8 3 3
1 0
2 7
2 2

输出样例 #1

8

输入样例 #2

5 1 3
1 0
1 2
1 4

输出样例 #2

9

输入样例 #3

10 2 2
1 10
2 10

输出样例 #3

0

提示

【样例说明】

只有一种方案，即在第一天走5步，第一、二步各获得1积分，第三、四步各获得2积分，第五步获得3积分，总计9积分。

说明/提示

对于10%的数据，n,m,k≤10。

对于40%的数据，n,m,k≤10^3。

对于100%的数据，1≤n≤10^12，1≤m,k≤10^5，1≤p≤m，0≤q≤n。

数据范围

一行1个整数，表示m天后最多可以获得的积分。

对于10%的数据，n,m,k≤10。

对于40%的数据，n,m,k≤10^3。

对于100%的数据，1≤n≤10^12，1≤m,k≤10^5，1≤p≤m，0≤q≤n。