题目描述
小蓝现在想用钱买一个纪念品,他的钱存在一个存钱罐里面(如果想要把存钱罐里面的钱拿出来就必须打破罐子),但是小蓝忘记存钱罐里面到底存了多少钱,小蓝想要知道存钱罐里面最少有多少钱。
我们知道空存钱罐和当前存钱罐的重量,还有每种钱对应的价值和重量,请帮小蓝完成这个任务。
输入描述
第一行是E和F,表示空罐和当前存钱罐的重量1 <= E <= F <= 10000。第二行有一个整数N(1 <= N <= 500)表示硬币的种类。接下来是N行,每行两个数 P和W(1 <= P <= 50000,1 <= W <= 10000)。 P表示硬币面值,W表示硬币重量。
输出描述
输出一个数,代表存钱罐最少的钱。
如果结果不存在,输出-1。
样例输入
10 110
2
1 1
30 50
样例输出
60
提示