One look at his alarm clock and Max knows he's going to be late—or is he? Luckily for Max, it's a late start today! But he better leave the house soon, else he will still be late...

School starts in ~N~ minutes, and Max quickly checks Google Maps for bus times. He finds ~M~ buses listed, with the ~i~-th bus scheduled to leave the station in ~L_i~ minutes. Each bus also differs in speed and number of stops, thus taking ~T_i~ minutes to arrive at WLMAC.

Assuming Max lives right beside the station, and that the time needed to walk from the bus stop to the school once he's arrived is negligible, what is the latest time Max can leave his house and still arrive at school on time? Note that Max will still arrive on time if he gets to school in exactly ~N~ minutes.

Constraints

~1 \le N, L_i, T_i \le 10^9~

~1 \le M \le 10^5~

Input Specification

The first line will contain two integers, ~N~ and ~M~.

The next ~M~ lines will each contain two integers, ~L_i~ and ~T_i~.

Output Specification

Output one integer, the latest time Max must leave his house to arrive at school on time. Output -1 if it is impossible for Max to arrive at school on time.

Sample Input 1

10 5
3 3
4 6
5 3
5 4
6 5

Sample Output 1

5

Sample Input 2

10 3
3 8
5 6
8 4

Sample Output 2

-1