#949. [Neerc2009]Business Center

[Neerc2009]Business Center

Description

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

Format

Input

第一行两个数n,m(1≤n≤1000000,1≤m≤2000),

接下来m行,每行两个数u_i和d_i (1≤u_i,d_i≤1000)。

Output

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

Samples

10 3
15 12
15 4
7 12
13