长征食粮
Description:
红军两万里长征，不仅仅是军事史上最伟大的业绩之一，也是人类历史上的伟大奇迹。这是一场战略撤退，使得红军的核心力量仍完整无损，其军心士气和政治意志的坚强显然一如往昔，使这个国家出现了许多世纪来所缺乏的精神与团结。那么在长征的过程中，食粮存储显得十分重要了，红军战士们需要携带符合自己体力上限的食粮物资。然而现在出现了一个问题，那就是食粮的单位热量都各不相同，战士们都希望能携带热量最高的食粮。聪明的ACMer，假如你成为了光荣的红军战士，你能想出携带食粮的最优方案吗？
Input:
输入的第一行有两个整数W（1 <= W <= 1000）和K（1 <= K <= 100），W代表自己所能携带的最大物资重量，K代表食粮物资数目。接下来的K行每行包括两个在1到100之间（包括1和100）的的整数，分别表示食粮的重量和其所蕴含的热量。
Output:
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以携带的食粮的热量的最大值。
Sample Input:
70 3 71 100 69 1 1 2
Sample Output:
3
Source:
Submit