벌목

Farmer John은 농장을 넓히고 있습니다. 수직선 위에 놓인 $N$그루의 나무($1 \le N \le 10^5$)로 이루어진 Red-Black Forest에서 이상적인 장소를 찾았습니다. $i$번째 나무의 위치는 $x_i$($-10^9 \le x_i \le 10^9$)입니다.

환경 보호법에 따라 농장을 만들기 위해 베어 낼 수 있는 나무가 제한됩니다. 제한 조건은 $K$개($1 \le K \le 10^5$)이며, 각 조건은 구간 $[l_i, r_i]$의 양 끝점을 포함해서 항상 최소 $t_i$그루($1 \le t_i \le N$)의 나무가 있어야 한다는 뜻입니다($-10^9 \le l_i \le r_i \le 10^9$). Red-Black Forest는 처음부터 이 조건들을 만족한다고 보장됩니다.

Farmer John은 농장을 최대한 크게 만들고 싶어 합니다. 모든 조건을 만족하면서 벨 수 있는 나무의 최대 개수를 구해 주세요.

입력은 $T$($1 \le T \le 10$)개의 독립된 테스트 케이스로 구성됩니다. 한 입력 안에서 모든 $N$의 합과 모든 $K$의 합은 각각 $3 \cdot 10^5$를 넘지 않습니다.

입력의 첫 줄에는 $T$가 주어집니다. 각 테스트 케이스의 형식은 다음과 같습니다.

첫 줄에는 정수 $N$과 $K$가 주어집니다.

다음 줄에는 $N$개의 정수 $x_1, \dots, x_N$이 주어집니다.

이어지는 $K$개의 줄에는 공백으로 구분된 세 정수 $l_i$, $r_i$, $t_i$가 각각 주어집니다.

각 테스트 케이스마다, Farmer John이 벨 수 있는 나무의 최대 개수를 나타내는 정수를 한 줄에 출력합니다.

첫 번째 테스트 케이스에서 Farmer John은 처음 $4$그루를 벨 수 있고, 위치 $x_i = 2, 6, 7$의 나무를 남기면 조건을 만족합니다.

두 번째 테스트 케이스에서는 추가된 조건이 벨 수 있는 나무에 영향을 주지 않으므로, 같은 나무를 베면 두 조건을 모두 만족합니다.

세 번째 테스트 케이스에서는 나무가 처음에 $7$그루 있는데, 두 번째 조건이 최소 $4$그루를 남기도록 요구하므로 Farmer John은 최대 $3$그루까지만 벨 수 있습니다.