{"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\"\u003e水箱里住着很多青蛙,但它们都不知道水箱里到底有多少水。\u003cbr\u003e\u003cbr\u003e水箱的高度是无限的,但底部很窄。水箱的长度是$N$,宽度只有$1$。\u003cbr\u003e\u003cbr\u003e现在有$N - 1$块木板将水箱分成了$N$部分,每部分都有一个$1 \\times 1$的底部。木板的高度可能不同。水不能流过木板,但如果水位更高,水就可以自由流动,遵循基本的物理规则。\u003cbr\u003e\u003cbr\u003e青蛙王想要了解水箱的更多细节,所以他派人选择$M$个位置,看看那些位置是否有水。\u003cbr\u003e\u003cbr\u003e例如,每次他会选择$(x, y)$,检查水箱的第$x^{th}$部分(从左到右数),然后查看高度为$(y + 0.5)$的位置是否有水。\u003cbr\u003e\u003cbr\u003e现在国王得到了$M$个结果,但他发现其中一些可能是错误的。国王想要找出可能的正确结果的\u003cb\u003e最大\u003c/b\u003e数量。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含一个整数$T$,表示测试用例的数量。\u003cbr\u003e\u003cbr\u003e每个测试用例以两个整数$N$和$M$开头,分别表示水箱的数量和结果的数量。\u003cbr\u003e\u003cbr\u003e每个测试用例的第二行包含$N - 1$个整数,$h_1$,$h_2$,$\\cdots$,$h_{N-1}$和$h_i$表示第$i^{th}$块木板的高度。\u003cbr\u003e\u003cbr\u003e然后是$M$行,每行格式为\u0027$x\\ y\\ z$\u0027,表示$i^{th}$的结果。如果在第$x^{th}$个水箱中高度为$(y + 0.5)$的位置没有水,则$z$为$0$,否则$z$为$1$。\u003cbr\u003e\u003cbr\u003e$\\cdot$ $1 \\leq T \\leq 100$。\u003cbr\u003e\u003cbr\u003e对于90%的数据,$1 \\leq N \\leq 1000$和$1 \\leq M \\leq 2000$。\u003cbr\u003e\u003cbr\u003e对于100%的数据,$1 \\leq N \\leq 10^5$和$1 \\leq M \\leq 2 \\cdot 10^5$。\u003cbr\u003e\u003cbr\u003e对于所有$1 \\leq i \\leq N - 1$,$\\cdot$。\u003cbr\u003e\u003cbr\u003e对于每个结果,$\\cdot$,$1 \\leq x \\leq N$和$1 \\leq y \\leq 10^9$要么是$0$要么是$1$。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,你应该输出\"\u003cb\u003eCase #x: y\u003c/b\u003e\",其中$x$表示案例编号,从$1$开始计数,$y$是可能的正确结果的最大数量。\u003cbr\u003e"}},{"title":"样例","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"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e在第一个样例中,如果第1个条件成立,那么第一部分的高度为3.5处会有水。水将流过高度为3的木板,所以第二部分的水位也应该与第一部分相同,这与第2个和第3个观察结果相矛盾。\u003cbr\u003e"}}]}