题目描述

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

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

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

输入格式

第一行：两个整数 $M$（工具箱最大承重，$1 \le M \le 10^4$）和 $N$（零件种类数，$1 \le N \le 10^4$）；

第 $2$ 到 $N+1$ 行：每行两个整数 $W_i, C_i$，分别表示第 $i$ 种零件的重量和价值（$1 \le W_i, C_i \le 100$）。

输出格式

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

输入输出样例

输入 #1

输出 #1

样例

输入

10 4

输出

2 1
3 3
4 5
7 9