【题意】

小明背着一个背包（最大能带的重量为 $T$ ）走进一个山洞，山洞里有 $n$ 种宝石（每种宝石无限多个），第 $i$ 种 宝石的重量为 $t_i$，拿到宝石店能卖 $m_i$ 块钱。

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

【输入文件】

第一行有两个整数 $T$（$1 \le T \le 1000$）和 $n$（$1 \le n \le 100$）。

下来 $n$ 行每行两个整数 $t_i$ 和 $m_i$（$0 \le t_i，m_i \le 100$）。

【输出文件】

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

【样例输入】

70 3
71 100
69 1
1 2

【样例输出】

140