Một chiếc bánh cần được rán trong đúng ~2N~ giây, trong đó mỗi mặt phải được rán đúng ~N~ giây.

Minh không thể lật bánh tại mọi thời điểm. Có ~K~ khoảng thời gian mà Minh có thể thực hiện việc lật bánh. Khoảng thứ ~i~ bắt đầu tại thời điểm ~l_i~ và kết thúc tại thời điểm ~r_i~, tính từ khi bắt đầu rán. Minh có thể lật bánh tại bất kỳ thời điểm nào thuộc đoạn ~[l_i,r_i]~.

Minh có thể lật bánh nhiều lần, miễn là khi kết thúc ~2N~ giây, mỗi mặt của bánh đã được rán đúng ~N~ giây.

Yêu cầu: Hãy xác định số lần lật bánh ít nhất cần thực hiện. Nếu không thể rán bánh đúng yêu cầu, hãy thông báo không thể thực hiện.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~K~ ~(1 \le N \le 5 \times 10^5;\ 1 \le K \le 100)~;

• Mỗi dòng trong ~K~ dòng tiếp theo gồm hai số nguyên ~l_i~ và ~r_i~ ~(0 \le l_i \le r_i \le 2N)~, cho biết Minh có thể lật bánh tại bất kỳ thời điểm nào thuộc đoạn ~[l_i,r_i]~;

• Dữ liệu bảo đảm ~l_i>r_{i-1}~ với mọi ~2 \le i \le K~.

Output

In ra số lần lật bánh ít nhất cần thực hiện. Nếu không thể thực hiện, in ra ~-1~.

Scoring

Sample Input 1

10 2
3 5
11 13

Sample Output 1

2

Sample Input 2

10 3
3 5
9 10
11 13

Sample Output 2

1