题目描述
现在一共有m的金币，有n种纸人，每种纸人都有无数个可供雇佣，雇佣第i种纸人需要花费的金币为w[i]、第i个纸人的战斗力为v[i]。那么最多能雇佣到战斗力之和为多少的纸人呢？
输入
输入第一行为空格隔开的两个整数，m、n，分别表示金币数量和纸人种数。（1 ≤ n ≤ 10000,1 ≤ m ≤ 10000000,1 ≤ n*m ≤ 10000000）
接下来n行，每行为空格隔开的两个整数，w[i]、v[i]，即雇佣第i种纸人花费的金币和第i种纸人的战斗力。（1 ≤ w[i],v[i] ≤ 10000）
输出
输出一行，为m的金币能雇佣到的最大的战斗力之和。
样例输入
70 3
71 100
69 1
1 2样例输出
140