Trên sân khấu có n đèn đươc đánh chỉ số từ 1 đến n, mỗi đèn có 3 trạng thái, trạng thái sáng màu xanh hoặc sáng màu đỏ hoặc tắt. Ban đầu tất cả các đèn đều ở trạng thái tắt.
Theo kịch bản sẽ có t lần thay đổi trạng thái của các đèn, lần thay đổi thứ k (k = 1,2, .., t) sẽ thay đổi trạng thái của tất cả các đèn có chỉ số từ ak đến ba (1 ≤ ak ≤ bk ≤ n). Với một đèn khi được thay đổi trạng thái sẽ thay đổi theo nguyên tắc như sau:
• Nếu đèn đang ở trạng thái tắt sẽ chuyển sang trạng thái sáng màu xanh
• Nếu đang ở trạng thái sáng màu xanh thì chuyển sang trạng thái sáng màu đỏ
• Nếu ở trạng thái sáng màu đỏ thì chuyển về trạng thái tắt
Ví dụ, nếu hệ thống gồm có 5 đèn và ban đầu đều ở trạng thái tắt, kịch bản gồm 3 thay đổi trạng thái các đèn, lần 1 thay đổi trạng thái các đèn có chỉ số từ 2 đến 4, lần 2 và lần 3 đều thay đổi trạng thái các đèn có chỉ số từ 3 đến 5. Khi đó, sau 3 lần thay đổi trạng cái của 5 đèn lần lượt là: tắt, sáng màu xanh, tắt, tắt, sáng màu đỏ.
Kết thúc buổi lễ, Ban tổ chức muốn thống kê số đèn ở trạng thái tắt sau t lần thay đổi trạng thái của các đèn theo kịch bản.
Yêu cầu: Cho biết kịch bản gồm t lần thay đổi trạng thái của các đèn, lần thay đổi thứ k (k = 1,2, ..., t) sẽ thay đổi trạng thái của tất cả các đèn có chỉ số từ ak đến bự. Hãy cho biết, khi kết thúc buổi lễ thì có bao nhiêu đèn ở trạng thái tắt.
Đầu vào:
• Dòng đầu chứa hai số nguyên dương n, t;
• Dòng thứ k trong t dòng tiếp theo chứa hai số nguyên dương ak, bk (1 ≤ ak ≤ bk ≤ n).
Kết quả: In ra một số nguyên là số lượng đèn tắt khi buổi lễ kết thúc.
Input:
5 3
2 4
3 5
3 5
Output:
3
Input:
1000 1
2 999
Output:
2
Chú ý:
Có 25% số test có n ≤ 10^6; t = 1;
Có 25% số test khác có n ≤ 10^3; t ≤ 10^5;
Có 40% số test khác có n ≤ 10^6; t ≤ 10^5;
Có 10% số test còn lại có n ≤ 10^9; t ≤ 10^5.
Bình luận