Một công ty lập trình lên một kế hoạch làm việc cho ~N~ ngày, với ~T~ dự án, dự án thứ ~i~ có thời gian kéo dài từ ngày thứ ~a_i~ đến ngày thứ ~b_i~. Các nhân viên phải đi làm trong thời gian công ty có dự án. Để đảm bảo số nhân viên làm việc và vẫn để nhân viên được nghỉ ngơi, công ty có quy định là những ngày không có dự án thì nhân viên được nghỉ và trong mỗi dự án nhân viên được nghỉ phép không quá một ngày.

Là một nhân viên lười biếng, Dino muốn nghỉ thật nhiều nhưng vẫn phải đúng luật của công ty, nên Dino sẽ lên kế hoạch nghỉ để mỗi dự án đều có chứa đúng một ngày nghỉ.

Em hãy lập trình giúp Dino tính xem theo kế hoạch trong ~N~ ngày của công ty và theo mong muốn của Dino thì được nghỉ tối đa bao nhiêu ngày?

Dữ liệu: Vào từ thiết bị nhập chuẩn

• Dòng đầu tiên chứa hai số nguyên ~N, T~ (~2 \le N, T \le 10^6~) tướng ứng là kế hoạch trong ~N~ ngày và ~T~ dự án của công ty.
• ~T~ dòng sau, dòng thứ ~i~ chứa hai số nguyên ~a_i~ và ~b_i~ mô tả thời gian bắt đầu và kết thúc dự án thứ ~i~ của công ty (~1 \le i \le T; 1 \le a_i \le b_i \le N~).

Kết quả: Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số ngày tối đa Dino có thể được nghỉ. Nếu không có cách chọn mà mỗi dự án đều có chứa đúng một ngày nghỉ thì in ra ~-1~.

Ví dụ:

Ràng buộc:

• Có 20% số lượng test ứng với 20% số điểm có ~2 \le N, T \le 20~;
• Có 20% số lượng test khác ứng với 20% số điểm có ~2 \le N, T \le 5000~;
• Có 30% số lượng test khác ứng với 30% số điểm có ~2 \le N, T \le 10^5~;
• Có 30% số lượng test còn lại ứng với 30% số điểm không có ràng buộc bổ sung.