{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"程序员小图和小灵一起去公园玩! 他们在有$n$棵树的公园里散步。他们调皮地要给公园里的树涂上颜色。树的编号是从$1$到$n$(从左往右数)的整数。\n\n一开始,第 i 棵树的颜色为 $c_i$。小图和小灵只能识别 $m$ 种不同的颜色,所以$c_i$的范围为 $0≤ c_i ≤m$,其中 $c_i \u003d 0$ 表示第 $i$ 棵树没有颜色。\n\n小图和小灵决定只给没有颜色的树上色,即 $c_i \u003d 0$ 的树。他们可以给每棵树上色任意颜色,颜色范围是从 $1$ 到 $m$ 。给第 $i$ 棵树上颜色 $j$ 正好需要 $P_{i,j}$ 升的油漆。\n\n他们将树的美观度定义为:相邻且颜色相同树组数量的最小值(每个树组包含树的颜色值的子段),也就是说,你可以将 $n$ 棵树分割为多个组,这样每个组包含相同颜色值的树。例如,如果树木的颜色从左到右依次为 $2, 1, 1, 1, 3, 2, 2, 3, 1, 3$ 那么美观度是$7$, 因为我们可以把这些树最少分割成 $7$ 组相邻且颜色相同的组: $\\\\{2\\\\}, \\\\{1 1 1\\\\}, \\\\{3\\\\}, \\\\{2,2\\\\}, \\\\{3\\\\}, \\\\{1\\\\}, \\\\{3\\\\}$ 。\n\n小图和小灵想给所有没有颜色的树上色,使树的美观度正好是 $k$ 。他们需要你的帮助来确定最少需要多少升油漆才能完成这项工作。\n\n注意不能给有颜色的树再上色。"}},{"title":"输入","value":{"format":"MD","content":"第 $1$ 行包含 $3$ 个整数,$n, m$ 和 $k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100) $—— 分别代表树的棵数,颜色的种数,最终着色的美观度。\n\n第 $2$ 行包含 $n$ 个整数 $c_1, c_2, ..., c_n (0 ≤ c_i ≤ m)$,代表每棵树最初的颜色值。 如果第 i 棵树的颜色值$c_i$ 等于 $0$ 意味着它没有被上色,否则第 $i$ 棵树有颜色 $c_i$.\n\n接下来的 $n$ 行输入里,每一行包含 $m$ 个整数:第 $i$ 行代表第 $i$ 棵树,这一行中第 $j$ 个位置的值代表上颜色 $j$ 需要用的油漆量$P_{i,j} (1 ≤ P_{i, j} ≤ 10^9)$。"}},{"title":"输出","value":{"format":"MD","content":"输出 $1$ 个整数 —— 代表给树上色需要的最少的油漆量。如果怎么上色都无法达到要求的美观度 $k$ ,那么输出 $- 1$."}},{"title":"样例","value":{"format":"MD","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n 输入\n \u003c/div\u003e\n \u003cpre\u003e3 2 2\u003cbr\u003e0 0 0\u003cbr\u003e1 2\u003cbr\u003e3 4\u003cbr\u003e5 6\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n 输出\n \u003c/div\u003e\n \u003cpre\u003e10\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n 输入\n \u003c/div\u003e\n \u003cpre\u003e3 2 2\u003cbr\u003e2 1 2\u003cbr\u003e1 3\u003cbr\u003e2 4\u003cbr\u003e3 5\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n 输出\n \u003c/div\u003e\n \u003cpre\u003e-1\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n 输入\n \u003c/div\u003e\n \u003cpre\u003e3 2 2\u003cbr\u003e2 0 0\u003cbr\u003e1 3\u003cbr\u003e2 4\u003cbr\u003e3 5\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n 输出\n \u003c/div\u003e\n \u003cpre\u003e5\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n 输入\n \u003c/div\u003e\n \u003cpre\u003e3 2 3\u003cbr\u003e2 1 2\u003cbr\u003e1 3\u003cbr\u003e2 4\u003cbr\u003e3 5\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n 输出\n \u003c/div\u003e\n \u003cpre\u003e0\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"提示","value":{"format":"MD","content":"在第 $1$ 个样例中,用$2,1,1$的颜色给树上色能使油漆使用量最小化,也就是$2 + 3 + 5 \u003d 10$。注意,$1,1,1$是无效的,因为这样上色的美观度等于$1$ ( $\\\\{1,1,1\\\\}$是将树分组成相邻且颜色相同的树组的一种方法 )。\n\n在第 $2$ 个样例中,所有的树都是有颜色的,并且美观度是 $3$ ,因此没办法改变树的颜色达到要求的美观度2,所以答案是 $-1$。\n\n在最后一个例子中,所有的树都是有颜色的,颜色的美观度已经与 $k$ 匹配,所以不需要使用油漆,答案是 $0$。"}}]}