Số ô tô đen

Cho hình chữ nhật kích thước 1xN ban đầu gồm toàn các ô màu trắng, cho lần lượt M thao tác có dạng u v nghĩa là cần tô đen các ô từ u đến v. Với mỗi thao tác chúng ta có hai lựa chọn:
Bỏ qua không làm thao tác này (sẽ không có ô nào được tô đen).
Tô đen từ ô u đến ô v khi và chỉ khi trong đoạn [u..v] chưa có ô nào được tô đen trước đó.
Yêu cầu: Tìm một cách thực hiện các thao tác sao cho số ô tô đen được là nhiều nhất có thể.
Input Format
Dòng đầu gồm 2 số N, M là số ô của hình chữ nhật và số thao tác (1 <= N, M <= 100)
M dòng tiếp theo mỗi dòng gồm hai số u v mô tả lần lượt các thao tác.
Output Format
Một số duy nhất là số ô tô được nhiều nhất
Sample Input
   5 3
   1 3
   2 4
   1 5
Sample Output
   5
Explanation
   Subtask 1: 30% số test có 1 # N # 100 , 1 # M # 15
   Subtask 2: 60% số test có 1 # N # 100 , 1 # M # 21
   Subtask 3: 100% số test có 1 # N, M # 100

                                                           Lời giải tham khảo