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