[Neerc2009]Business Center

时间限制:1s      空间限制:128MB

题目描述

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

提示

没有写明提示


题目来源

没有写明来源