0
已解决
资深光能
5086 雕刻宝石经验值：0
题目描述 Description
璀璨靓丽，光彩夺目的宝石，总是那么吸引人的注意力。所以，酷町猫立志成为一名优秀的宝石雕刻师，现在摆在酷町猫面前有很多宝石，雕刻每一种宝石都要花费一定的时间，且每种宝石对应着不同的价值；
现在给酷町猫一定的时间T，问酷町猫如何选择在这一段时间内如何选择雕刻宝石才会使得,雕刻宝石的总价值最大？
输入描述 Input Description
第一行有两个整数T（1< =T < =4000）和M（1〈=M〈=10000），用一个空格隔开，T代表总共能够用来雕刻宝石的总时间，M代表现在拥有的宝石的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示做出雕刻某种宝石的时间和这个宝石的价值。
输出描述 Output Description
包括一行，这一行只包含一个整数，表示在规定的时间内，可以雕刻的宝石的最大总价值。
样例输入 Sample Input
70 3 71 100 69 1 1 2
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
T<=4000, m<=10000
对于全部的数据，m〈=10000
