题目描述

小明背着一个背包（最大能带的重量为 $V$）走进一个山洞。

山洞里有 $n$ 种 宝石（每种宝石无限多个），第 $i$ 种 宝石的重量为 $v_i$，拿到宝石店能卖 $m_i$ 块钱。

求在背包能承受重量的范围内，使得小明装进背包的宝石总价值最大。

输入格式

第一行有两个整数 $V$ 和 $n$。

接下来的n行每行两个整数 $v_i$ 和 $m_i$。

输出格式

输出一行，一个整数，即最大总价值。

70 3
71 100
69 1
1 2

140

数据规模与约定

对于 $30\%$ 的数据，$n\le 10$；

对于 $100\%$ 的数据，$n\le 100$，$1\le V\le 1000$，$0\le v_i,m_i\le 100$。