给出一个长度为 n n n 宽度为 1 1 1，高度无限的水箱，有 n−1 n - 1 n−1 个挡板将其分为 n n n 个 1 - 1 的小格，然后向每个小格中注水，水如果超过挡板就会溢出到挡板的另一边，这里的水是满足物理定律的（在无挡板阻拦的情况下会向低处流），现在有 m m m 个条件 (i,y,k) (i, y, k) (i,y,k)，表示从左到右数的第 i i i 个格子中，在高度为 y+0.5 y + 0.5 y+0.5 的地方是否有水，k=1 k = 1 k=1 表示有水，k=0 k = 0 k=0 表示没有水，请求出这 m m m 个条件最多能同时满足多少个条件。本题有多组数据。
第一行一个正整数 T T T，为数据组数。
第二行两个正整数 n n n、m m m，中间用空格隔开。
接下来一行 n−1 n - 1 n−1 个整数，表示从左到右每一块隔板的高度。
接下来 m m m 行，每行三个整数 i i i、y y y、k k k，表示一个条件。
共 T T T 行，每行对应一组数据的答案。
2
3 4
3 4
1 3 1
2 1 0
2 2 0
3 3 1
2 2
2
1 2 0
1 2 1
3
1
对于 20% 20\% 20% 的数据，n,m≤16 n, m \leq 16 n,m≤16；
对于另外 10% 10\% 10% 的数据，只存在指明某处有水的条件；
对于另外 30% 30\% 30% 的数据，n,m≤1000 n, m \leq 1000 n,m≤1000；
对于 100% 100\% 100% 的数据，n,m≤105,T≤5 n, m \leq 10 ^ 5, T \leq 5 n,m≤105,T≤5。