题目描述

小泽在接下来的 $m$ 天里总共至多走 $n$ 步。有 $k$ 条积分规则：规则 $(p,q)$ 表示第 $p$ 天走完前 $q$ 步后，当天此后的每一步额外获得 $1$ 分。多条规则可以叠加。小泽可任意分配每天步数，求最高总分。

输入格式

第一行三个整数 $n,m,k$。接下来 $k$ 行每行两个整数 $p,q$。

输出格式

输出最高总分。

输入

157913 33 8
24 54041
5 11137
30 8360
7 122021
18 153693
22 103477
2 153097
3 96916

输出

149553

输入

266520 14 22
12 201095
14 239534
2 105907
7 2217
1 111577
13 211500
5 206986
2 140879
9 161464
14 147393
9 120872
6 140528
9 59541
4 15981
10 127092
5 249113
5 262251
1 48755
8 130132
7 9975
1 250834
3 93860

输出

520848

输入

963442 32 23
9 732125
11 551787
2 234450
26 657367
8 256591
11 163477
32 240345
7 524302
27 356005
22 894922
28 499914
14 826552
16 217365
6 843705
22 43258
11 814482
3 160070
15 680276
31 732728
25 11299
15 128035
12 435819
30 469522

输出

1360580

数据范围

$1\le n\le10^{12}$，$1\le m,k\le10^5$，$1\le p\le m$，$0\le q\le n$。