题目描述

小x有一个容量为c的背包，可以装c公斤的物品，现在小x面临一个选择，但是小x是选择困难症，请你帮助他。
有m个物品 每个物品重量为w[i]（公斤，保证每个w[i]为整数）价值为p[i]（保证每个p[i]为整数）
到底怎么选择，才能在不超过背包容量的情况下获取价值最大呢？

输入

第一行:两个整数 c,m
其余m行：每行两个整数 分别代表重量和价格

输出

一个整数，即小x能获得的最大价值

样例输入

10 4
2 1
3 3
4 5
7 9

样例输出

12

提示

对于100%数据 不会超出int范围