火柴被安排的明明白白：每个箱子中装的每盒火柴的根数都是相同的。即：有m个箱子，对于第i个箱子：其中有a_i盒火柴，每盒火柴都有b_i根。现在，你可以拿走其中n盒，这n盒最多包含多少根火柴？

第一行，有单个空格分隔的两个整数n,m，分别表示能拿走的盒数和共有多少箱火柴。

接下来m行，每行有单个空格分隔的两个整数{a_i},{b_i}，分别表示这箱火柴有多少盒、每盒有多少根。

对于100%的数据：

1\le m \le 20 ；

1\le n\le 2\cdot 10^8 ；

1\le {a_i} \le 10^8 ；

1\le {b_i} \le 10 。

一行，一个整数，表示最多能拿走的火柴根数。