{"trustable":false,"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":"MD","content":"丁丁妹妹有一个无限高的存钱罐,底部长N,宽度为1,由N-1个高度分别为hi隔板隔成底部为1*1的小室,丁丁妹妹喜欢往里面放硬币,硬币不能穿过隔板,但如果某个小室中硬币的高度高于某个与之相邻的小室的隔板的高度,会从高处向低处滑落。ZHY想要知道存钱罐中硬币的分别情况,于是排出M个人去侦察,(x,y)代表该个侦查宾侦查第x个小室(从左往右),高度为y+0.5处有没有硬币,如有为1,没有为0,但是有些人说的是对的有些是错的。问最多有可能有多少侦察兵返回的正确的消息?"}},{"title":"Input","value":{"format":"MD","content":"第一行一个数T代表测试的组数\n每一组数据第一行两个整数代表N,M\n接下来一行N-1个数代表每个隔板的高度,从左往右\n接下来M行每行三个数 X Y Z,代表(x,y)处返回的情况\n1≤N≤1e5 and 1≤M≤2e5.\n1≤hi≤1e9 for all 1≤i≤N−1.\nT\u003c\u003d100\n且%90的数据 N\u003c\u003d1e3,M\u003c\u003d2e3"}},{"title":"Output","value":{"format":"MD","content":"每一组数据输出\" Case #x: y\"的形式"}},{"title":"Sample Input","value":{"format":"MD","content":"2\n3 4\n3 4\n1 3 1\n2 1 0\n2 2 0\n3 3 1\n2 2\n2\n1 2 0\n1 2 1"}},{"title":"Sample Output","value":{"format":"MD","content":"Case #1: 3\nCase #2: 1\n\n \n"}},{"title":"Hint","value":{"format":"MD","content":"第一组\n选择2,3,4人说的是对的,因为如果第一个人说的是对的话,那么3.5的高度\u003e3,则2号室中高度1.5,2.5处应该有硬币与2,3人相悖"}}]}