D. E09_1*【背包：价值填满型完全背包】山洞宝石2

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

小明背着一个背包（最大能带的重量为 $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$ ）。

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