题目描述
为了在选拔赛中取得优异成绩,各位选手一定经过了长时间的集训。在训练过程中,每位同学都在尽量多的解决题目,以努力取得最好的成绩为荣。
假设在训练过程中,众多题目可分为N种题型,在这里给出解决每种题型中一道试题的分值和时间(暂认为解决同题型的题目所得的分值及花费的时间相同)。请你合理安排一下在集训有限的时间M(分钟)内你能得到的最高成绩是多少?
100%:1<=M,N,Pi,Ti<=10000
输入格式
第一行:一个空格间隔的两个整数,分别是集训的时间M、题型数N;
第二行至N+1行:第i+1行有一个空格间隔的两个整数,分别表示解决该题型一道题目可得到的分值Pi和解决所需要的时间Ti。
输出格式
仅一个整数,为合理安排训练时间,取得的最高分数。
样例输入
样例输出