Description

小$G$将在沙漠中发现一片巨大的油田的好消息告诉了小$L$后，小$L$便为石油的开采做准备，由于要在沙漠之中建造一座全新的炼油厂来提炼采好石油，所以小$L$最先准备的是建造炼油厂的材料，然后再准备开采机器的材料。

准备好建造炼油厂的材料后，小$L$发现新的问题：现在家中剩余的材料不够合成足量的预期型号的开采机器（不同型号的开采机器所消耗材料不同且效率是不同的）。为了化简题目，我们认为合成开采机器的材料只有铁锭一种，并且油田的储量是无限，于是小$L$想用剩余的铁锭来合成出合适型号的开采机器，使得开采油田的效率和达到最大。小$L$想请你来设计一个程序来求当前情况下开采油田的所能达到的最大效率和。

PS:在铁锭充足的情况下，每种开采机器都可以无限制作。

Input Format

对于每个测试用例，第一行输入两个整数 $n$ 和 $m$，$n$ 表示铁锭的数量，$m$ 表示机器的种类。

第二到 $m+1$ 行，每行两个整数，第 $i+1$ 行的整数 $a_i,b_i$ 分别表示第 $i$ 种开采机器需要的铁锭数量和开采效率。

题目的数据范围：$1 \le m \le 10^4, 1 \le n \le 10^7$，$1 \le n \times m \le 10^7$, $1 \le a_i, b_i \le 10^4$。

Output Format

对于每个测试用例，输出一行，这一行只包含一个整数，表示开采油田所需机器的总效率，即最大开采效率和。

5 4
1 2
2 4
3 4
4 5

10

Source

Online Judge http://127.0.0.1