Ryo là một cảnh sát trưởng vô cùng tài ba. Vì không gặp thuận lợi lắm trong chuyện tình cảm nên Ryo rất tức giận mỗi khi nhìn thấy các cặp đôi đi chơi với nhau. Lễ Giáng Sinh cũng đang đến rất gần rồi nên Ryo quyết định sẽ điều động cảnh sát đi canh chốt ở một số các tuyến phố để nhằm
phá hoại các cặp đôi không chú ý khi tham gia giao thông (đương nhiên điều đó làm Ryo thấy rất vui!).
Thành phố mà Ryo sinh sống có tuyến phố được đánh số từ đến . Vì là cảnh sát trưởng nên có cảnh sát mà Ryo có thể điều động, đánh số từ đến . Cảnh sát thứ khi được điều động sẽ canh chốt ở các tuyến phố có số hiệu từ đến . Tất nhiên các cặp đôi đi chơi Giáng Sinh không chỉ đi duy nhất một ngày nên Ryo quyết định sẽ cho cảnh sát canh chốt ở ngày liên tiếp. Khổ nỗi, tất cả các cảnh sát đều có việc riêng của mình nên mỗi người sẽ chỉ canh chốt vào một ngày duy nhất thôi. Nhưng vì không thể từ bỏ khao khát phá hoại hạnh phúc các cặp đôi nên Ryo lên kế hoạch như sau: Ryo sẽ chọn chỉ số và điều động tất cả cảnh sát có chỉ số từ đến đi canh chốt vào ngày , tất cả cảnh sát có chỉ số từ đến canh chốt vào ngày và tất cả cảnh sát có chỉ số từ đến canh chốt vào ngày .
Việc phân bố lực lượng để canh chốt trong ba ngày là một điều hết sức khó khăn. Độ tốt của một ngày là số lượng tuyến phố phân biệt bị canh chốt bởi ít nhất một cảnh sát đi canh trong ngày đó.
Bạn hãy tìm cách giúp Ryo phân bố cảnh sát sao cho tổng độ tốt của cả ba ngày là lớn nhất nhé!
Dữ liệu vào:
Dòng đầu tiên bao gồm hai số nguyên dương là số lượng cảnh sát và số lượng tuyến phố;
dòng tiếp theo, dòng thứ bao gồm số nguyên và miêu tả phạm vi làm việc của cảnh sát thứ .
Dữ liệu ra:
Gồm một số nguyên dương là tổng độ tốt lớn nhất của cả ngày.
Ví dụ:
Dữ liệu vào:
8 9
1 2
1 3
3 3
1 6
5 6
3 3
1 2
6 9
Dữ liệu ra:
17
Giải thích: Chọn hoặc .
Giới hạn:
Subtask số điểm có ;
Subtask số điểm khác có ;
Subtask số điểm khác có ;
Subtask số điểm còn lại không có điều kiện gì thêm.
