Có một đường thẳng có độ dài $N-1$. Mục tiêu là đi từ vị trí $1$ trên đường thẳng đến vị trí $N$ trong thời gian ngắn nhất. Tổng cộng có $T$ phút, mỗi phút sẽ xảy ra một sự kiểm soát.

Sự kiểm soát ở phút thứ $t$ được cho bởi hai số nguyên $l_t, r_t$. Nếu tại thời điểm $t+0.5$, vị trí $x$ của bạn thỏa mãn $l_t \le x \le r_t$, bạn sẽ thất bại ngay lập tức. Nếu $t > T$, sẽ không có sự kiểm soát nào xảy ra.

Mỗi phút, bạn có thể di chuyển đến ô liền kề hoặc đứng yên tại vị trí hiện tại. Bạn sẽ đạt được mục tiêu ngay khi đến vị trí $N$.

Nếu tồn tại cách để đến vị trí $N$ mà không thất bại, hãy in ra thời gian ngắn nhất có thể, nếu không tồn tại, hãy in ra -1.

Dữ liệu vào

Dòng đầu tiên chứa độ dài của đường thẳng $N$. $(1 \le N \le 2 \times 10^5)$

Dòng thứ hai chứa tổng thời gian xảy ra kiểm soát $T$. $(1 \le T \le 2 \times 10^5)$

Từ dòng thứ ba trở đi, mỗi dòng trong số $T$ dòng chứa hai số nguyên $l_t, r_t$ cách nhau bởi dấu cách. $(1 \le l_t \le r_t \le N)$

Dữ liệu ra

In ra thời gian ngắn nhất. Nếu không tồn tại, in ra -1.

Ví dụ

Dữ liệu vào 1

4
4
2 4
1 1
2 2
3 3

Dữ liệu ra 1

4

Dữ liệu vào 2

5
3
2 5
3 4
1 4

Dữ liệu ra 2

-1