{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eA lot of frogs are living in a water tank, but none of them know exactly how much water are there.\u003cbr\u003e\u003cbr\u003eThe water tank has an infinite height, but with a narrow bottom. The length of the tank is $N$, and the width is only $1$.\u003cbr\u003e\u003cbr\u003eNow $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.\u003cbr\u003e\u003cbr\u003eThe Frog King wants to know more details of the tank, so he sent someone to choose $M$ positions and find whether there\u0027s water at that position.\u003cbr\u003e\u003cbr\u003eFor example, each time he\u0027ll 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\u0027s water at height $(y + 0.5)$.\u003cbr\u003e\u003cbr\u003eNow the King gets $M$ results, but he finds some of them might be wrong. The King wants to find out the \u003cb\u003emaximum\u003c/b\u003e possible number of the correct results.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"First line contains an integer $T$, which indicates the number of test cases.\u003cbr\u003e\u003cbr\u003eEvery test case begins with two integers $N$ and $M$, which is the numbers of tanks and numbers of results.\u003cbr\u003e\u003cbr\u003eThe 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\u0027s height.\u003cbr\u003e\u003cbr\u003eThen $M$ lines follow, the $i^{th}$ line, formated as \u0027$x\\ y\\ z$\u0027, 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$.\u003cbr\u003e\u003cbr\u003e$\\cdot$ $1 \\leq T \\leq 100$.\u003cbr\u003e\u003cbr\u003e$\\cdot$ For 90% data, $1 \\leq N \\leq 1000$ and $1 \\leq M \\leq 2000$\u003cbr\u003e\u003cbr\u003e$\\cdot$ for 100% data, $1 \\leq N \\leq 10^5$ and $1 \\leq M \\leq 2 \\cdot 10^5$.\u003cbr\u003e\u003cbr\u003e$\\cdot$ $1 \\leq h_i \\leq 10^9$ for all $1 \\leq i \\leq N - 1$.\u003cbr\u003e\u003cbr\u003e$\\cdot$ for every result, $1 \\leq x \\leq N$, $1 \\leq y \\leq 10^9$ and $z$ is either $0$ or $1$."}},{"title":"Output","value":{"format":"HTML","content":"For every test case, you should output \"\u003cb\u003eCase #x: y\u003c/b\u003e\",where $x$ indicates the case number and counts from $1$, and $y$ is the maximum possible number of the correct results.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 4\r\n3 4\r\n1 3 1\r\n2 1 0\r\n2 2 0\r\n3 3 1\r\n2 2\r\n2\r\n1 2 0\r\n1 2 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 3\r\nCase #2: 1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIn the first sample case, if the 1-st condition is true, then there\u0027s 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.\u003cbr\u003e"}}]}