CF711C.Coloring Trees

ZS the Coder and Chris the Baboon has arrived at Udayland! They walked in the park where n trees grow. They decided to be naughty and color the trees in the park. The trees are numbered with integers from 1 to n from left to right.

Initially, tree i has color c__i. ZS the Coder and Chris the Baboon recognizes only m different colors, so 0 ≤ c__i ≤ m, where c__i = 0 means that tree i is uncolored.

ZS the Coder and Chris the Baboon decides to color only the uncolored trees, i.e. the trees with c__i = 0. They can color each of them them in any of the m colors from 1 to m. Coloring the i-th tree with color j requires exactly p__i, j litres of paint.

The two friends define the beauty of a coloring of the trees as the minimum number of contiguous groups (each group contains some subsegment of trees) you can split all the n trees into so that each group contains trees of the same color. For example, if the colors of the trees from left to right are 2, 1, 1, 1, 3, 2, 2, 3, 1, 3, the beauty of the coloring is 7, since we can partition the trees into 7 contiguous groups of the same color : {2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}.

ZS the Coder and Chris the Baboon wants to color all uncolored trees so that the beauty of the coloring is exactly k. They need your help to determine the minimum amount of paint (in litres) needed to finish the job.

Please note that the friends can't color the trees that are already colored.

ZS 程序员和 Chris 猕猴抵达了乌代兰！他们在公园里散步，公园中有 $ n $ 棵树。他们决定调皮一下，给公园里的树涂色。这些树从左到右依次编号为 $ 1 $ 到 $ n $。

初始时，第 $ i $ 棵树的颜色为 $ c_i $。ZS 程序员和 Chris 猕猴仅能识别 $ m $ 种不同颜色，因此 $ 0 \leq c_i \leq m $；其中 $ c_i = 0 $ 表示第 $ i $ 棵树尚未着色。

ZS 程序员和 Chris 猕猴决定只对未着色的树（即满足 $ c_i = 0 $ 的树）进行涂色。他们可以将每棵未着色的树涂成 $ 1 $ 到 $ m $ 中的任意一种颜色。将第 $ i $ 棵树涂成颜色 $ j $ 恰好需要 $ p_{i,j} $ 升油漆。

两位朋友将一棵树着色方案的“美观度”定义为：将全部 $ n $ 棵树划分为最少数量的连续段（每一段包含一个连续子序列的树），使得每一段内的所有树颜色相同。例如，若从左到右各棵树的颜色依次为 $ 2,,1,,1,,1,,3,,2,,2,,3,,1,,3 $，则该着色方案的美观度为 $ 7 $，因为我们可将这些树划分为如下 $ 7 $ 个同色连续段：$ {2},,{1,,1,,1},,{3},,{2,,2},,{3},,{1},,{3} $。

ZS 程序员和 Chris 猕猴希望将所有未着色的树染色，使得最终着色方案的美观度恰好为 $ k $。他们需要你的帮助，来确定完成这项任务所需的最小油漆用量（单位：升）。

请注意：朋友们不能对已经着色的树重新涂色。

The first line contains three integers, n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of trees, number of colors and beauty of the resulting coloring respectively.

The second line contains n integers _c_1, _c_2, ..., c__n (0 ≤ c__i ≤ m), the initial colors of the trees. c__i equals to 0 if the tree number i is uncolored, otherwise the i-th tree has color c__i.

Then n lines follow. Each of them contains m integers. The j-th number on the i-th of them line denotes p__i, j (1 ≤ p__i, j ≤ 109) — the amount of litres the friends need to color i-th tree with color j. p__i, j's are specified even for the initially colored trees, but such trees still can't be colored.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq k \leq n \leq 100$，$1 \leq m \leq 100$），分别表示树的数量、颜色种类数以及最终染色方案的“美观度”。

第二行包含 $n$ 个整数 $c_1,\,c_2,\,\dots,\,c_n$（$0 \leq c_i \leq m$），表示每棵树的初始颜色。若 $c_i = 0$，则表示第 $i$ 棵树尚未染色；否则第 $i$ 棵树的初始颜色为 $c_i$。

接下来有 $n$ 行，每行包含 $m$ 个整数。其中第 $i$ 行的第 $j$ 个数表示 $p_{i,j}$（$1 \leq p_{i,j} \leq 10^9$），即为第 $i$ 棵树染上第 $j$ 种颜色所需消耗的升数。即使对于已预先染色的树，其所有 $p_{i,j}$ 值也均被给出，但这些已染色的树仍不可再次染色。

Print a single integer, the minimum amount of paint needed to color the trees. If there are no valid tree colorings of beauty k, print  - 1.

输出一个整数，表示给树木染色所需的最少油漆量。如果不存在美丽值为 $k$ 的合法树木染色方案，则输出 $-1$。

In the first sample case, coloring the trees with colors 2, 1, 1 minimizes the amount of paint used, which equals to 2 + 3 + 5 = 10. Note that 1, 1, 1 would not be valid because the beauty of such coloring equals to 1 ({1, 1, 1} is a way to group the trees into a single group of the same color).

In the second sample case, all the trees are colored, but the beauty of the coloring is 3, so there is no valid coloring, and the answer is  - 1.

In the last sample case, all the trees are colored and the beauty of the coloring matches k, so no paint is used and the answer is 0.

在第一个样例中，将树木染成颜色 $2,\,1,\,1$ 可使所用颜料量最小，其值为 $2\,+\,3\,+\,5\,=\,10$。注意，染色方案 $1,\,1,\,1$ 是不合法的，因为该染色方案的“美观度”为 $1$（$\{1,\,1,\,1\}$ 表示可将所有树木划分为一个同色组）。

在第二个样例中，所有树木均已染色，但该染色方案的“美观度”为 $3$，因此不存在合法染色方案，答案为 $-1$。

在最后一个样例中，所有树木均已染色，且该染色方案的“美观度”恰好等于 $k$，因此无需使用颜料，答案为 $0$。