8159: BZOJ4159：[Neerc2009]Business Center

M部电梯，开始都在0层，第i部电梯每次可以上u_i层楼，或下d_i层楼，求第i部电梯这样上下n次后，这个电梯最低能停在哪层(最终要在1层或以上)。并取最小值输出。(m≤2000,n≤1000000)

输入格式

第一行两个数n,m（1≤n≤1000000,1≤m≤2000）, 接下来m行，每行两个数u_i和d_i （1≤u_i,d_i≤1000）。

输出格式

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

样例输入

10 3
15 12
15 4
7 12

样例输出

13

提示

没有写明提示

题目来源

没有写明来源