P11453 [USACO24DEC] Deforestation S

Farmer John 正在扩大他的农场！他已经找到了完美的位置——红黑森林，由数轴上的 $N$ 棵树（$1≤N≤10^5$）组成，第 $i$ 棵树位于位置 $x_i$（$−10^9≤x_i≤10^9$）。 环境保护法限制了 Farmer John 可以砍伐哪些树来为他的农场腾出空间。有 $K$ 个限制（$1≤K≤10^5$），规定在线段 $[l_i,r_i]$（包含端点）中必须始终至少存在 $t_i$ 棵树（$−10^9≤l_i,r_i≤10^9$）。输入保证红黑森林初始时满足这些限制。 Farmer John 想要他的农场尽可能大。请帮助他计算他可以砍伐的树的最大数量，同时仍然满足所有限制！

每个测试点包含 $T$（$1≤T≤10$）个独立的测试用例。输入保证一个测试点中的所有 $N$ 之和以及 $K$ 之和均不超过 $3⋅10^5$。 输入的第一行包含 $T$。每个测试用例的格式如下： - 第一行包含整数 $N$ 和 $K$。 - 下一行包含 $N$ 个整数 $x_1,\cdots,x_N$。 - 以下 $K$ 行，每行包含三个空格分隔的整数 $l_i$，$r_i$ 和 $t_i$。

对于每个测试用例，输出一行，包含一个整数，表示 Farmer John 可以砍伐的树的最大数量。

### 样例解释 对于第一个测试用例，Farmer John 可以砍伐前 $4$ 棵树，留下位于 $x_i=2,6,7$ 的树来满足限制。 对于第二个测试用例，额外的限制不会影响 Farmer John 可以砍伐哪些树，因此他可以砍伐相同的树并同时满足两个限制。 对于第三个测试用例，Farmer John 至多只能砍伐 $3$ 棵树，因为初始时有 $7$ 棵树，但第二个限制要求他至少留下 $4$ 棵树不砍伐。 ### 测试点性质 测试点性质： - 测试点 1：样例。 - 测试点 2：$N,K≤16$。 - 测试点 3-5：$N,K≤1000$。 - 测试点 6-7：对于所有的 $i=1,\cdots,K$ 有 $ti=1$。 - 测试点 8-11：没有额外限制。