题目描述

给出一个长度为 $n$ 宽度为 $1$，高度无限的水箱，有 $n - 1$ 个挡板将其分为 $n$ 个 $1 \times 1$ 的小格，然后向每个小格中注水，水如果超过挡板就会溢出到挡板的另一边，这里的水是满足物理定律的（在无挡板阻拦的情况下会向低处流）。现在有 $m$ 个条件 $(i, y, k)$，表示从左到右数的第 $i$ 个格子中，在高度为 $y + 0.5$ 的地方是否有水，$k = 1$ 表示有水，$k = 0$ 表示没有水。请求出这 $m$ 个条件最多能同时满足多少个条件。本题有多组数据。

输入格式

第一行一个正整数 $T$，为数据组数。
第二行两个正整数 $n$、$m$，中间用空格隔开。
接下来一行 $n - 1$ 个整数，表示从左到右每一块隔板的高度。
接下来 $m$ 行，每行三个整数 $i$、$y$、$k$，表示一个条件。

输出格式

共 $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\%$ 的数据，$n, m \leq 16$；
对于另外 $10\%$ 的数据，只存在指明某处有水的条件；
对于另外 $30\%$ 的数据，$n, m \leq 1000$；
对于 $100\%$ 的数据，$n, m \leq 10^5$，$T \leq 5$。