题目描述

$m$ 部电梯，开始都在 $0$ 层，第 $i$ 部电梯每次可以上 $u_i$ 层楼，或下 $d_i$ 层楼，求第 $i$ 部电梯这样上下 $n$ 次后，这个电梯最低能停在哪层（最终要在 $1$ 层或以上），并取 $m$ 个数中的最小值输出。

输入格式

第一行两个数 $n,m$，接下来 $m$ 行，每行两个数 $u_i$ 和 $d_i$。

输出格式

输出一个正整数——这 $m$ 个电梯中某一个在正好按了 $n$ 次以后，可以到达的最底层。

10 3
15 12
15 4
7 12

13

数据规模与约定

对于 $100\%$ 的数据，$1\leq m\leq 2\times 10^3$，$1\leq n\leq 10^6$，$1\leq u_i,d_i\leq 10^3$。