Business Center#522
International Cyber Police Corporation (ICPC) has built a new mega-tall business center to host its headquarters and to lease some space for extra profit. There are so many floors that it is impractical to have a separate button in each of its elevator cars for each individual floor. Instead, each elevator car has just two buttons. In the -th elevator car, one button moves it up u_i floors, and the other button moves it down d_i floors. The business center is so tall that we can ignore its height for this problem (you will never reach the top floor), but you cannot go below the ground floor. All floors are numbered by integer values starting from zero, where zero is the ground floor.
You start on the ground floor of the business center. You must choose one of the elevator cars to use. After making your choice, you cannot switch elevators. What is the lowest floor above the ground floor you can reach after pressing the elevator's buttons exactly times?
The first line of the input file contains two integers and (1 \le n \le 1\ 000\ 000, 1 \le m \le 2000) — the number of button presses and the number of elevator cars to choose from. The following lines describe the elevators. Each line contains two integers u_i and d_i (1 \le u_i, d_i \le 1\ 000).
Print a single positive integer — the number of the lowest floor above the ground floor that can be reached by one of the elevators after pressing its buttons exactly times.
Example 1