Sangkeun Tower

Time limit1sMemory limit128 MB

Summary

For each elevator, find the minimum floor above 0 reachable using exactly n button presses (up/down moves), never going below 0, then take the overall minimum across elevators.

Level: Medium5 of 10
Topics: Dynamic programming, Brute force, Math
Solved: No attempts yet

Problem

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.

Input

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$ )

Output

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

Examples4

Example 1
Input
```
10 3
15 12
15 4
7 12
```
Expected output
```
13
```
Example 2
Input
```
1 1
5 3
```
Expected output
```
5
```
Example 3
Input
```
2 1
1 1
```
Expected output
```
2
```
Example 4
Input
```
5 4
10 3
2 9
7 7
100 1
```
Expected output
```
7
```