说明

学姐又要去Google上班了，这一次学姐想多做几道水题，并使题目的总水量最大.学姐同一时刻只能在水一道题，只有做完这道题才能得到它的水值，学姐的总时间为t，现在一共有n道题，编号从1到n，每道题有两个值a和b，a为做这道题需要的时间，b为题目的水值。

输入格式

数据中第一行为两个数t和n，n为题目的数量，t为总时间,接下来n行,每行两个正整数a和b。(1≤a,t≤1000，1≤n≤100，1≤b≤1000000)

输出格式

输出对应的最大总水量。

10 2
8 16
6 12

16

来源

基本算法