Một thành phố hiện đại sử dụng hệ thống đèn giao thông tự động với N nút đèn, được đánh số từ 1 đến N.

Mỗi nút đèn có thể ở một trong ba trạng thái:

• 0 – đèn đỏ (dừng).
• 1 – đèn xanh (đi).
• 2 – đèn vàng (chờ).

Ban đầu, tất cả các nút đèn đều ở trạng thái đỏ (0).

Trong quá trình điều khiển, trung tâm giao thông thực hiện T lần điều chỉnh đồng bộ. Ở lần điều chỉnh thứ i (i = 1, 2, …, T), tất cả các nút đèn từ vị trí aᵢ đến bᵢ (1 ≤ aᵢ ≤ bᵢ ≤ N) sẽ đồng loạt chuyển sang trạng thái tiếp theo theo vòng tuần hoàn:

• Đèn đỏ (0) → chuyển sang xanh (1).
• Đèn xanh (1) → chuyển sang vàng (2).
• Đèn vàng (2) → trở lại đỏ (0).

Ví dụ: Giả sử có 5 nút đèn giao thông được bố trí dọc theo một tuyến phố. Ban đầu, tất cả đều đang đỏ (0). Trung tâm thực hiện 3 lần điều chỉnh như sau:

• Lần 1: thay đổi các nút từ vị trí 2 đến 4.
• Lần 2: thay đổi các nút từ vị trí 3 đến 5.
• Lần 3: tiếp tục thay đổi các nút từ vị trí 3 đến 5.

Sau 3 lần điều chỉnh, trạng thái cuối cùng của 5 nút đèn lần lượt là: 0, 1, 0, 0, 2.

Điều đó có nghĩa là:

• Nút 2 hiện ở xanh (1) → xe được phép đi.
• Nút 5 hiện ở vàng (2) → xe chuẩn bị dừng.
• Các nút 1, 3, 4 ở đỏ (0) → xe phải dừng lại.

Kết quả: có 3 nút đèn vẫn ở trạng thái đỏ.

Yêu cầu bài toán: Sau khi thực hiện T lần điều chỉnh, hãy cho biết có bao nhiêu nút đèn đang ở trạng thái đỏ (0).

Dữ liệu vào: Từ thiết bị chuẩn có định dạng như sau:

• Dòng đầu tiên chứa hai số nguyên dương N, T ~(1 ≤ N ≤ 10^9, 1 ≤ T ≤ 10^5)~.
• Trong T dòng tiếp theo, dòng thứ i chứa hai số nguyên dương ~a_i, b_i~ ~(1 ≤ a_i ≤ b_i ≤ N)~.

Kết quả: Ghi ra thiết bị chuẩn một số nguyên duy nhất là số lượng ô có trạng thái 0 sau khi thực hiện xong T lần thay đổi.

Ví dụ:

Dữ liệu vào

5 3
2 4
3 5
3 5

Kết quả

3

Ràng buộc:

• Có 25% số test tương ứng với 25 điểm có ~N ≤ 10^6~; T = 1
• Có 25% số test tương ứng với 25 điểm có ~N ≤ 10^3~; ~T ≤ 10^5~
• Có 40% số test tương ứng với 40 điểm có ~N ≤ 10^6~; ~T ≤ 10^5~
• Có 10% số test tương ứng với 10 điểm có ~N ≤ 10^9~; ~T ≤ 10^5~