【模板】完全背包-滚动数组优化
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
仓库里有 种零件，每种零件都有无限多个。第 种零件的重量为 ，价值为 。
工人师傅有一个最大承重为 的工具箱，他想在不超过工具箱承重的前提下，选择若干个零件（可以选同一种零件多次），使得所选零件的总价值最大。
请你帮工人师傅计算这个最大总价值。
输入格式
第一行：两个整数 和 ，分别表示工具箱最大承重和零件种类数。
接下来 行：每行两个整数 ，分别表示第 种零件的重量和价值。
输出格式
一行，一个整数，表示最大总价值。
10 4
2 1
3 3
4 5
7 9
12
样例解释 最优方案：选一个重量为 价值为 的零件，再选一个重量为 价值为 的零件，总重量 ，总价值 。可以证明这是最大值。