Lập trình Robot AI

Trong cuộc thi trí tuệ nhân tạo ROAI2025, Ban tổ chức yêu cầu các đội chơi lập trình Robot AI trên sân đấu trong môi trường thực tế ảo tham chiếu trên hệ trục tọa độ $Oxy$. Mỗi đội chơi cần đặt 2 con Robot AI tại 2 điểm phân biệt trên đường thẳng $y=2$ với tọa độ $x$ là số nguyên trong phạm vi từ $0$ tới $N$. Mỗi Robot AI có một mắt thần có nhiệm vụ quan sát đường thẳng $y=0$.

Sàn đấu có hai tấm chắn biên là các đoạn thẳng $AB$ và $CD$ với tọa độ: $A(0,2)$, $B(0,1)$, $C(N,1)$, $D(N,2)$. Ban tổ chức đặt thêm $K$ tấm chắn khác là những đoạn thẳng nằm trên đoạn $BC$. Tấm chắn thứ $i$ trong số $K$ tấm chắn bắt đầu từ điểm $(L_i,1)$ và kết thúc ở điểm $(R_i,1)$.

Robot AI tại điểm $U$ trên đường thẳng $y=2$ chỉ quan sát được những điểm $V$ trên đường thẳng $y=0$ nếu như đoạn thẳng $UV$ không giao với bất kỳ đoạn thẳng là tấm chắn nào trong số $K+2$ tấm chắn trên. Một đoạn trên đường thẳng $y=0$ gọi là quan sát được nếu như mọi điểm trên đoạn đó (ngoại trừ 2 đầu mút) đều quan sát được. Nhiệm vụ của mỗi đội chơi là cần đặt được 2 con Robot AI sao cho tổng độ dài các đoạn quan sát được trên đường thẳng $y=0$ bởi ít nhất một Robot AI là lớn nhất có thể.

Yêu cầu: Đội tuyển của Tuấn lần đầu tiên tham gia thi tài, hãy giúp đội của Tuấn tìm ra cách đặt tối ưu cho 2 con Robot AI.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $K$ ($1\le N\le {10}^9$; $1\le K\le 2000$).
• Dòng thứ $i$ trong số $K$ dòng tiếp theo chứa hai số nguyên $L_i$ và $R_i$ ($0\le L_i<R_i\le N$).

Dữ liệu bảo đảm $L_1<R_1<L_2<R_2<\dots <L_K<R_K$. Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng độ dài các đoạn quan sát được trên đường thẳng $y=0$ trong phương án tối ưu tìm được.

Ràng buộc

• $1\le N\le {10}^9$; $1\le K\le 2000$.
• $0\le L_i<R_i\le N$; $L_1<R_1<L_2<R_2<\dots <L_K<R_K$.

Subtasks

• Subtask 1 ($16\%$ số điểm): $N\le 200$.
• Subtask 2 ($16\%$ số điểm): $N\le 2000$; $K\le 20$.
• Subtask 3 ($20\%$ số điểm): $N\le 20000$.
• Subtask 4 ($20\%$ số điểm): $K\le 500$.
• Subtask 5 ($28\%$ số điểm): không có ràng buộc nào thêm.

Ví dụ