Logo Quest Online Judge

QOJ

时间限制:1 s 空间限制:256 MB
统计

题目描述

给出一个长度为 $ n $ 宽度为 $ 1 $,高度无限的水箱,有 $ n - 1 $ 个挡板将其分为 $ n $ 个 1 - 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 $。