84434 - 零食大作战
时间限制 : 1 秒
内存限制 : 128 MB
小明有 C 元零花钱，想去便利店买零食。便利店里有 n 种零食，每种零食的库存都是无限的，第 i 种零食单价为w_i元，吃一个能获得的快乐值为v_i。 小明希望在不超支的前提下，买到总快乐值尽可能高的零食组合，请你帮他算一算最多能获得多少快乐值。
输入
第一行两个正整数 C 和 n，分别表示零花钱总额和零食种类数。
接下来 n 行，每行两个正整数 w_i，v_i分别表示第 i 种零食的单价和快乐值。
输出
一个整数，表示最多能获得的快乐值。
样例
输入
10 2 2 3 3 5
输出
16
提示
对于 100% 的数据，1≤C≤1000，1≤n≤100，1≤w_i≤100，1≤v_i≤1000。
来源
入门教程