2019年第二阶段我要变强个人训练赛第十三场问题 C:魔理沙的烟火制造（二分）

我要变强个人训练赛第十三场问题 C:魔理沙的烟火制造（二分）"/>

2019年第二阶段我要变强个人训练赛第十三场问题 C:魔理沙的烟火制造（二分）

传送门

题目描述

在魔法森林，最有名的两个建筑物就是玛格特洛依德邸和雾雨邸。
这个问题便是雾雨邸的主人，雾雨魔理沙，在制造以星尘为原料的烟火时遇到的。
魔理沙一共想要制造T个烟火。她现在有n种星尘，用第i种材星尘制造一个烟火的花费为ci份星尘。由于同种星尘之间的排斥，每次用第i种星尘制造了一个烟火之后，下一次使用同种星尘制造一个烟火的花费会增加di。
幸运的是，魔理沙还有另外一种特别的，不会发生排斥的星尘。每次用这种星尘制造一个烟火，都要花费P份星尘。
收集星尘，即使是对于一个不需要借助任何物品就能飞行的人类而言，也不是一件容易的事。所以魔理沙想知道，制造所有的T个烟火，她至少要多少的星尘。

输入

第一行三个整数，代表T,P,n。
接下来n行，每行两个整数，代表ci,di。

输出

一行一个正整数代表答案。

样例输入

8 16 3 1 5 2 4 3 3

样例输出

43

提示

分别用1,2,3种星尘制造2,3,3个烟火，代价为1+6+2+6+10+3+6+9=43

一开始想到的是二分答案，但是想了好久没想出来怎么写