{"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\"\u003eArcSoft, Inc. is a leading global professional computer photography and computer vision technology company.\u003cbr\u003e\u003cbr\u003eThere are $N$ working blocks in ArcSoft company, which form a straight line. The CEO of ArcSoft thinks that every block should have equal number of employees, so he wants to re-arrange the current blocks into $K$ new blocks by the following two operations:\u003cbr\u003e\u003cbr\u003e- merge two neighbor blocks into a new block, and the new block\u0027s size is the sum of two old blocks\u0027.\u003cbr\u003e- split one block into two new blocks, and you can assign the size of each block, but the sum should be equal to the old block.\u003cbr\u003e\u003cbr\u003eNow the CEO wants to know the \u003cb\u003eminimum\u003c/b\u003e operations to re-arrange current blocks into $K$ block with equal size, please help him.\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 one line which two integers $N$ and $K$, which is the number of old blocks and new blocks.\u003cbr\u003e\u003cbr\u003eThe second line contains $N$ numbers $a_1$, $a_2$, $\\cdots$, $a_N$, indicating the size of current blocks.\u003cbr\u003e\u003cbr\u003eLimits\u003cbr\u003e$1 \\leq T \\leq 100$\u003cbr\u003e$1 \\leq N \\leq 10^5$\u003cbr\u003e$1 \\leq K \\leq 10^5$\u003cbr\u003e$1 \\leq a_i \\leq 10^5$"}},{"title":"Output","value":{"format":"HTML","content":"For every test case, you should output \u003cb\u003e\u0027Case #x: y\u0027\u003c/b\u003e, where \u003cb\u003ex\u003c/b\u003e indicates the case number and counts from \u003cb\u003e1\u003c/b\u003e and \u003cb\u003ey\u003c/b\u003e is the minimum operations.\u003cbr\u003e\u003cbr\u003eIf the CEO can\u0027t re-arrange $K$ new blocks with equal size, \u003cb\u003ey\u003c/b\u003e equals \u003cb\u003e-1\u003c/b\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\u003e3\r\n1 3\r\n14\r\n3 1\r\n2 3 4\r\n3 6\r\n1 2 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: -1\r\nCase #2: 2\r\nCase #3: 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}