题目描述

小明带着1个容量不超过2000千克的背包，到超市采购物品，假设超市内有n种物品（n不超过100），每件物品重量wi和价值vi，每种物品提供的数量无限制。请问小明如何采购，才能确保在不超背包容量的前提下获得最大的价值。

输入格式

第一行2个整数，m和n，代表背包的容量和物品的种数。 第2行到第n+1行，每行2个整数代表第i种物品的重量wi和价值vi。

输出格式

在不撑破背包容量下能获得的最大价值

样例

input

10 3

5 7

3 5

4 3

output

15