【模板】完全背包
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
完全背包是经典的动态规划问题，在实际生活与算法竞赛中均有广泛应用。
题目描述
设有 种物品，每种物品有一个重量及一个价值。每种物品的数量是无限的，同时有一个背包，最大载重量为 。今从 种物品中选取若干件（同一种物品可以多次选取），使其重量的和不超过 ，而价值的和为最大。
输入格式
第一行两个整数 和 ，分别表示背包容量和物品种类数。
接下来 行，每行两个整数 ，分别表示第 种物品的重量和价值。
输出格式
输出一行，max=一个整数，表示最大总价值。
12 4
2 3
3 4
4 5
5 6
max=18
提示
样例解释
全选第一个物品