벌목 timer 1초 memory 1024MB

입력은 여러 개의 테스트 케이스로 이루어져 있습니다. 각 테스트 케이스는 다음과 같습니다:

• 첫 번째 줄에 테스트 케이스의 수 T가 주어집니다. (1≤T≤10).

• 각 테스트 케이스는 다음과 같은 형식으로 이루어집니다:

  1. 첫 번째 줄에 정수 N과 K가 주어집니다. (1 ≤ N,K ≤ 10^5)

     • N의 합과 K의 합은 각각 3⋅10^5을 넘지 않음이 보장된다.

  2. 두 번째 줄에는 N개의 정수 x_1, x_2, \cdots, x_N이 주어집니다. (−10^9 ≤ x_i ≤ 10^9)

  3. 이후 K개의 줄에 걸쳐 각 제한 구간이 주어지며, 각 제한은 세 개의 정수 l_i, r_i, t_i로 이루어져 있습니다. (−10^9 ≤ l_i ≤ r_i ≤ 10^9; 1 ≤ t_i ≤ N)

각 테스트 케이스에 대해, 나무꾼 존이 자를 수 있는 최대 나무의 수를 한 줄에 출력합니다.

첫 번째 테스트 케이스에서는 농부 존이 첫 번째 4개의 나무를 자를 수 있으며, 나무 위치가 x_i=2, 6, 7인 나무를 남겨 두어 제한을 만족시킬 수 있습니다.

두 번째 테스트 케이스에서는 추가적인 제한이 농부 존이 자를 수 있는 나무에 영향을 미치지 않으므로, 그는 동일한 나무들을 자르면서 두 제한을 모두 만족할 수 있습니다.

세 번째 테스트 케이스에서는 농부 존이 최대 3개의 나무만 자를 수 있습니다. 처음에는 7개의 나무가 있지만 두 번째 제한에 따라 최소 4개의 나무는 자르지 않고 남겨야 하기 때문입니다.