Farmer John đang mở rộng trang trại! Ông đã tìm ra địa điểm hoàn hảo trong Rừng Đỏ-Đen, gồm \(N\) cây (\(1\leq N\leq 10^5\)) trên một trục số, cây thứ \(i\) nằm tại vị trí \(x_i\) (\(-10^9\leq x_i\leq 10^9\)).

Luật bảo vệ môi trường hạn chế những cây Farmer John có thể chặt để lấy chỗ cho trang trại. Có \(K\) ràng buộc (\(1\leq K\leq 10^5\)), mỗi ràng buộc quy định rằng luôn phải có ít nhất \(t_i\) cây (\(1\leq t_i\leq N\)) trong đoạn \([l_i,r_i]\), tính cả hai đầu mút (\(-10^9\leq l_i\leq r_i\leq 10^9\)). Đảm bảo ban đầu Rừng Đỏ-Đen thỏa mãn các ràng buộc này.

Farmer John muốn trang trại của mình lớn nhất có thể. Hãy giúp ông tính số cây tối đa có thể chặt mà vẫn thỏa mãn mọi ràng buộc!

Dữ liệu vào

Mỗi đầu vào gồm \(T\) (\(1\leq T\leq 10\)) bộ test độc lập. Đảm bảo tổng tất cả các giá trị \(N\) và tổng tất cả các giá trị \(K\) trong một đầu vào đều không vượt quá \(3\cdot 10^5\).

Dòng đầu chứa \(T\). Sau đó, mỗi bộ test có định dạng:

• Dòng đầu chứa hai số nguyên \(N\) và \(K\).
• Dòng tiếp theo chứa \(N\) số nguyên \(x_1,\dots,x_N\).
• Mỗi dòng trong \(K\) dòng tiếp theo chứa ba số nguyên cách nhau bởi dấu cách: \(l_i\), \(r_i\) và \(t_i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa một số nguyên là số cây tối đa Farmer John có thể chặt.

Phân nhóm

• Test 2: \(N,K\leq 16\).
• Các test 3–5: \(N,K\leq 1000\).
• Các test 6–7: \(t_i=1\) với mọi \(i=1,\dots,K\).
• Các test 8–11: Không có ràng buộc bổ sung.

Ví dụ

3
7 1
8 4 10 1 2 6 7
2 9 3
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
7 2
8 4 10 1 2 6 7
2 9 3
1 10 4

4
4
3

Nguồn

Đề bài gốc: USACO 2024 December Contest, Silver — Deforestation

Tác giả: Tina Wang, Jiahe Lu, Benjamin Qi.