KizaHM sau khi kiếm được một chút tiền từ việc làm bác sĩ, phù thủy,... Hôm nay anh quyết định dành cho mình một ngày nghỉ.

Ngồi bật TV và xem thời sự, anh thấy báo chí đưa tin về những em nhỏ trên vùng cao có cuộc sống rất khó khăn. Do đó anh đã quyết định gọi cho những người bạn của mình là Jozu, Louis, Grenore, Skynet và muốn mọi người cùng nhau đi làm từ thiện. Các bạn đều đồng ý với quyết định của KizaHM.

Hội bạn nhận định rằng những trẻ em ở càng vùng cao thì càng khó khăn, do đó quyết định lần này sẽ đi làm từ thiện cho các em nhỏ ở huyện Sapa - tỉnh Lào Cai, nơi có đỉnh Phan-Xi-Păng cao nhất Đông Nam Á.

Chuyến này đi, các bạn quyết định sẽ đến n địa điểm (~n \le 10^8~) để làm từ thiện, mỗi địa điểm có một độ cao là ~h_i (1 \le i \le n, h_i  \le 10^8)~ và 2 địa điểm cạnh nhau có chiều cao chênh lệch không quá 1. Khổ nỗi là trên cao, thông tin bị nhiễu nên thiết bị của họ chỉ lưu đúng m địa điểm (~1 \le m \le 100000~) và chiều cao của mỗi địa điểm đó.

Các bạn hãy giúp KizaHM tính xem nơi cao nhất mà KizaHM và các bạn có thể đến có chiều cao bao nhiêu.

Input

• Dòng đầu tiên gồm hai số ~n~ và ~m~.
• m dòng sau mỗi dòng gồm 2 số ~d_i~ là vị trí các địa điểm còn lưu theo thứ tự tăng dần và ~h_{d_i}~ là chiều cao tại các địa điểm đó

Output

Một dòng duy nhất là chiều cao của nơi cao nhất nhóm bạn có thể đến, nếu không có kết quả thỏa mãn thì in ra màn hình -1

Sample

Input #1

8 2
2 0
7 0

Output #1

2

Input #2

8 3
2 0
7 0
8 3

Output #2

-1

Problem source: CLB Lập Trình PTIT