完全背包

题目描述

你有一个容量为 V 的背包，以及 n 种物品。第 i 种物品的体积为 w_i，价值为 val_i。

每种物品都有无限件，你可以选择任意多件放入背包，但总容量不能超过 V。

请你求出在不超过背包容量的前提下，能获得的最大总价值。

输入

第一行两个整数 V, n，表示背包容量与物品种类数。

接下来 n 行，每行两个整数 w_i, val_i，分别表示第 i 种物品的体积与价值。

输出

先输出max=，再输出一个整数，表示最大总价值。。

样例

提示

对于 40\% 的数据，1\le n \le 8，1\le V \le 12，且对所有 i，1\le w_i \le 1000，0\le val_i \le 1000。

对于 100\% 的数据，1\le n \le 1000，1\le V \le 1000，且对所有 i，1\le w_i \le 1000，0\le val_i \le 1000。

来源

一本通