Ma trận sắc màu

Ở một miền quê sông nước hẻo lánh, đoàn BigO dưới sự dẫn dắt của thầy giáo làng cùng các “cánh tay phải” của mình đang chu du thiên hạ để chinh phục những bài toán khó trong truyền thuyết.

Họ đã đi một quãng đường dài mà vẫn chưa tìm được vị cao nhân nào để thỉnh giáo. Trời đã ngả trưa, cả đoàn nghe theo lời dặn của thầy giáo làng, dừng chân dùng bữa trưa tại Halidao – một quán ăn nức tiếng thời bấy giờ. Đối diện quán ăn là một dãy gồm n hàng rào được xếp thứ tự từ trên xuống dưới, tất cả đều có cùng độ dài $10^9 + 7$ và hiện đều mang màu trắng. Tại đây, họ gặp một cụ ông năm nay đã 120 tuổi nhưng trông vẫn còn rất khỏe mạnh.

Tiếng lành đồn xa nên ai nấy đều biết đến BigO (và dĩ nhiên cụ ông cũng biết). Cụ liền đứng dậy ngay khi thấy thầy giáo làng vừa đặt chân vào quán. Cụ lớn tiếng thách đố: “Hỡi chàng trai trẻ, ta biết cậu và những người học trò đầy tiềm năng của mình đang đi tìm kiếm các thử thách. Ta có một câu đố đã cất giữ bấy lâu nay và muốn thách đấu cậu!”.

Đôi mắt thầy giáo sáng lên và nhận lời thách đấu không chút do dự. Dưới đây là câu đố của cụ ông:

“Hãy tìm cách dỡ bỏ ít hàng rào nhất có thể sao cho những hàng rào còn lại, khi giữ nguyên thứ tự sắp xếp từ trên xuống dưới, tạo thành một mạng lưới hàng rào đẹp.”

Cụ ông cho biết một mạng lưới hàng rào đẹp là mạng lưới mà bất kỳ 2 hàng liên tiếp nào cũng phải có ít nhất một cột chung cùng được tô màu đỏ.

Cho biết hiện có n hàng rào được xếp từ trên xuống dưới và có m thao tác tô màu. Mỗi thao tác tô màu được mô tả bởi ba số nguyên $id, l, r$, nghĩa là các cột từ l đến r ở hàng rào thứ id sẽ được tô màu đỏ.

Nhiệm vụ của thầy giáo làng là xác định số lượng hàng rào tối thiểu cần dỡ bỏ sau khi tô màu để thu được một mạng lưới hàng rào đẹp.

Đầu vào:

• Dòng đầu tiên chứa hai số nguyên n và m - số lượng hàng rào và số thao tác tô màu.

• m dòng tiếp theo, mỗi dòng chứa 3 số nguyên $id, l, r$ - thao tác tô màu đỏ cho đoạn từ cột l đến r ở hàng rào có chỉ số id.

• Các đoạn tô màu có thể chồng lấn lên nhau; một ô có thể được tô màu nhiều lần.

• $1 \leq$ $n, m$ $\leq 10^5$

• $1 \leq$ id $\leq n$

• $1 \leq$ l $\leq r$ $\leq 10 ^ 9 + 7$

Đầu ra: Một dòng duy nhất in ra hai số nguyên k - số lượng hàng rào tối thiểu cần dỡ bỏ và chỉ số kết thúc sớm nhất (nhỏ nhất) trong các dãy hàng rào đẹp có độ dài $n - k$ được chọn (ví dụ: nếu có 2 cách chọn dãy hàng rào đẹp là $(1,2,4,6)$ và $(1,2,5,7)$, ta chọn dãy đầu tiên với chỉ số kết thúc sớm nhất là 6). Lưu ý: hàng rào không có ô nào được tô đỏ thì không được giữ lại trong dãy được chọn.

$25\%$ số test: $1\leq n, m \leq 1000$.

$75\%$ số test còn lại: Giới hạn như trong đề bài.

Giải thích:

• Ví dụ 1: Dãy hàng rào được chọn có chỉ số là $1 - 3$ hoặc $2 - 3$.

• Ví dụ 2: Dãy hàng rào được chọn có chỉ số là $1 - 2 - 3$.

Ví dụ 1:

Đầu vào:

5 4
1 2 3
2 4 6
3 3 5
5 1 1

Đầu ra:

3 3

Ví dụ 2:

Đầu vào:

3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15

Đầu ra:

0 3