题目描述

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 可以砍伐的树的最大数量。

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

提示

样例解释

对于第一个测试用例，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：没有额外限制。