Lật bánh

Minh muốn dùng bữa. Anh ấy vừa trở về từ cửa hàng, nơi anh ấy mua một chiếc bánh rán, việc còn lại chỉ là rán chín lên. Dòng chữ trên bao bì nói rằng chiếc bánh cần được rán trong chảo ở lửa vừa phải trong chính xác $2\times N$ giây: rán chính xác $N$ giây ở một mặt và chính xác $N$ giây ở mặt còn lại. Minh đã tìm được một chiếc chảo và đốt lửa vừa phải, nhưng sau đó anh nhận ra rằng mình có thể không lật được chiếc bánh đúng vào thời điểm $N$ giây sau khi bắt đầu rán.

Minh quá bận rộn và chỉ có thể lật bánh ở một số thời điểm nhất định. Cụ thể, có $K$ khoảng thời gian mà anh ấy có thể lật bánh, khoảng thứ $i$ bắt đầu từ thời điểm $l_i$ giây đến thời điểm $r_i$ giây kể 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]$ (kể cả hai đầu mút). Mỗi lần lật diễn ra tức thời; tại mỗi thời điểm, mặt đang nằm dưới chảo là mặt được rán.

Minh quyết định rằng không cần thiết phải lật bánh đúng một lần, thay vào đó anh có thể lật nhiều lần, miễn là khi kết thúc $2\times N$ giây, mỗi mặt của chiếc bánh đã được rán đúng $N$ giây.

Yêu cầu: Hãy giúp Minh xác định liệu anh có thể hoàn thành kế hoạch hay không khi chỉ được lật bánh trong các khoảng thời gian đã cho, và nếu được thì số lần lật bánh ít nhất cần thực hiện là bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $K$ $(1\le N\le 5\times {10}^5,1\le K\le 100)$.
• $K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$ $(0\le l_i\le r_i\le 2\times N)$, nghĩa là Minh có thể lật bánh tại bất kỳ thời điểm nào trong đ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$.

Dữ liệu ra

In ra 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, in ra $-1$.

Ràng buộc

• $1\le N\le 5\times {10}^5$
• $1\le K\le 100$
• $0\le l_i\le r_i\le 2\times N$; $l_i>r_{i-1}$ với mọi $2\le i\le K$

Subtasks

• Subtask 1 ($20\%$ số test): $N\le 10$.
• Subtask 2 ($20\%$ số test): $N\le 1000$.
• Subtask 3 ($20\%$ số test): kết quả không quá $2$ lần lật.
• Subtask 4 ($20\%$ số test): $N\le {10}^5$.
• Subtask 5 ($20\%$ số test): không có ràng buộc gì thêm.

Ví dụ