你有一个容量为 $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$。