Sangkeun Tower

Sangkeun used his leftover money to build a very tall building called “Sangkeun Tower”.

Sangkeun Tower has $m$ elevators. Each elevator has two buttons. For the $i$-th elevator, one button goes up $u_i$ floors and the other button goes down $d_i$ floors.

The bottom floor (the lobby) of Sangkeun Tower is floor 0, and the floors above it are numbered with increasing natural numbers (floor 1, floor 2, and so on). An elevator can never go below floor 0 (underground), and the building is so tall that it has no top.

Sangkeun is standing in the lobby. He now picks exactly one elevator and boards it. Once he boards an elevator, he cannot switch to another one. Write a program that finds the lowest floor (excluding the lobby) he can reach by pressing the buttons of the chosen elevator exactly $n$ times.

The first line contains $n$ and $m$. ($1 \le n \le 1{,}000{,}000$, $1 \le m \le 2{,}000$) Each of the next $m$ lines contains $u_i$ and $d_i$ for one elevator, separated by a space. ($1 \le u_i, d_i \le 1{,}000$)

Print the lowest floor that can be reached by pressing an elevator's buttons exactly $n$ times. The lobby (floor 0) is excluded.