题目描述

仓库里有 $N$ 种零件，每种零件都有无限多个。第 $i$ 种零件的重量为 $W_i$，价值为 $C_i$。

工人师傅有一个最大承重为 $M$ 的工具箱，他想在不超过工具箱承重的前提下，选择若干个零件（可以选同一种零件多次），使得所选零件的总价值最大。

请你帮工人师傅计算这个最大总价值。

输入格式

第一行：两个整数 $M$ 和 $N$，分别表示工具箱最大承重和零件种类数。

接下来 $N$ 行：每行两个整数 $W_i, C_i$，分别表示第 $i$ 种零件的重量和价值。

输出格式

一行，一个整数，表示最大总价值。

样例

10 4
2 1
3 3
4 5
7 9

12

样例解释
最优方案：选一个重量为 $7$ 价值为 $9$ 的零件，再选一个重量为 $3$ 价值为 $3$ 的零件，总重量 $7+3=10$，总价值 $9+3=12$。可以证明这是最大值。

数据范围

• $1 \le M \le 10^4$
• $1 \le N \le 10^4$
• $1 \le W_i, C_i \le 100$