题目背景

小 W 下载了一款运动软件。

题目描述

小 W 准备在接下来的 $m$ 天中锻炼，由于他不能走得太多以至于累死（怎么可能呢），所以他这 $m$ 天最多一共只能走 $n$ 步。
这个运动软件为了激励小 W 走路，推出了 $k$ 种激励措施，每种激励措施都形如“如果你第 $p$ 天走完了 $q$ 步，那么第 $p$ 天中接下来的每一步都会给你加 $1$ 积分”。激励措施可以叠加，即走一步你可能可以获得多于 $1$ 积分。
现在小 W 想知道，他最多可以获取多少积分呢？

输入格式

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

输出格式

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

5 1 3
1 0
1 2
1 4

9

提示

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

数据范围：
对于 $10\%$ 的数据，$n,m,k\le10$。
对于 $40\%$ 的数据，$n,m,k \le 10^3$。
对于 $100\%$ 的数据，$1\le n\le 10^{12}$，$1\le m,k\le 10^5$，$1\le p\le m$，$0\le q\le n$。