Background

设有 $n$ 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 $M$ ，今从 $n$ 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于 $M$ ，而价值的和为最大。

Format

Input

第一行：两个整数，$M$(背包容量，$M\le 200$)和 $N$(物品数量，$N\le 30$)；

第 $2\dots N+1$ 行：每行二个整数 $w_i$ ,$c_i$ ，表示每个物品的重量和价值。

Output

输出仅一行。首先输出"max="（输出不含引号），后面输出一个数，表示最大总价值。（中间不含空格）

可参考样例的输出格式。

Samples

输入 #1

10  4
2  1
3  3
4  5
7  9

输出 #1

max=12

# Limitation

1s, 1024KiB for each test case.