Phá Rừng

Farmer John đang phát triển đất nông nghiệp trong Khu Rừng Đỏ-Đen chứa $N$ cây trên trục số. Mỗi cây $i$ nằm tại vị trí $x_i$. Các quy định môi trường đặt ra $K$ ràng buộc: mỗi ràng buộc yêu cầu ít nhất $t_i$ cây phải còn lại trong đoạn $[l_i,r_i]$. Khu rừng ban đầu thỏa mãn tất cả ràng buộc. Tìm số cây tối đa có thể chặt mà vẫn đảm bảo tất cả ràng buộc.

Dữ liệu vào

• Dòng đầu: $T$ ($1\le T\le 10$) là số test case.
• Mỗi test case:
  • Dòng $1$: Hai số nguyên $N$ và $K$.
  • Dòng $2$: $N$ số nguyên $x_1,x_2,\dots ,x_N$ - vị trí các cây.
  • $K$ dòng tiếp theo: Ba số nguyên $l_i$, $r_i$, $t_i$.
• $1\le N\le {10}^5$, $1\le K\le {10}^5$, $-{10}^9\le x_i,l_i,r_i\le {10}^9$.
• Tổng $N$ và tổng $K$ qua tất cả test case $\le 3·{10}^5$.

Dữ liệu ra

Mỗi test case in ra một số nguyên - số cây tối đa có thể chặt.

Ràng buộc

• Test $2$-$3$: $N,K\le 16$
• Test $4$-$5$: $N,K\le 1000$
• Test $6$-$7$: Tất cả $t_i=1$
• Test $8$-$11$: Không có ràng buộc thêm

Ví dụ