Discover Water Tank

A lot of frogs are living in a water tank, but none of them know exactly how much water are there.

The water tank has an infinite height, but with a narrow bottom. The length of the tank is $N$, and the width is only $1$.

Now $N - 1$ boards has divided the tank into $N$ parts, each with an $1 \times 1$ bottom. Boards may have different heights. Water cannot flow through the boards, but can run freely if the water level is higher, following the basic physical rules.

The Frog King wants to know more details of the tank, so he sent someone to choose $M$ positions and find whether there's water at that position.

For example, each time he'll choose$(x, y)$, checking the $x^{th}$ part of the tank($1 \leq x \leq N$), counting from left to right, and find whether there's water at height $(y + 0.5)$.

Now the King gets $M$ results, but he finds some of them might be wrong. The King wants to find out the maximum possible number of the correct results.

First line contains an integer $T$, which indicates the number of test cases.

Every test case begins with two integers $N$ and $M$, which is the numbers of tanks and numbers of results.

The second line of each test case contains $N - 1$ integers, $h_1$, $h_2$, $\cdots$, $h_{N-1}$, and $h_i$ indicates the height of $i^{th}$ board's height.

Then $M$ lines follow, the $i^{th}$ line, formated as '$x\ y\ z$', indicates $i^{th}$ result. $z$ is $0$ if there is no water at height $(y + 0.5)$ in $x^{th}$ tank, otherwise $z$ is $1$.

$\cdot$ $1 \leq T \leq 100$.

$\cdot$ For 90% data, $1 \leq N \leq 1000$ and $1 \leq M \leq 2000$

$\cdot$ for 100% data, $1 \leq N \leq 10^5$ and $1 \leq M \leq 2 \cdot 10^5$.

$\cdot$ $1 \leq h_i \leq 10^9$ for all $1 \leq i \leq N - 1$.

$\cdot$ for every result, $1 \leq x \leq N$, $1 \leq y \leq 10^9$ and $z$ is either $0$ or $1$.

For every test case, you should output "Case #x: y",where $x$ indicates the case number and counts from $1$, and $y$ is the maximum possible number of the correct results.

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

Case #1: 3
Case #2: 1

In the first sample case, if the 1-st condition is true, then there's water at height 3.5 in the first part. The water will run over the board with height 3, so the water level in the second part should also be the same as the first part, which contradicts the 2-nd and 3-rd observation.

2015ACM/ICPC亚洲区上海站-重现赛（感谢华东理工）