题目描述

小e的背包容量为m，现在商店里有n种商品。

由于在梦境中，他可以零元购，商店里的每种商品都有无穷件，每件商品有一个价值w_i和体积v_i。

问小e最多可以带走多少价值的商品？

输入格式

第一行两个整数表示m, n。(1 \le m \le 10^5, 1 \le n \le 500)

接下来n行，每行两个整数表示w_i, v_i。(1 \le w_i \le 10^9, 1\le v_i \le m)

输出格式

一行一个整数表示答案。

样例输入1

10 3
2 1
5 3
10 4

样例输出1

24

解释：拿两件物品3，再拿两件物品1，得到价值最大为24。