CF711C Coloring Trees

ZS the Coder 和 Chris the Baboon 来到了 Udayland！他们在公园里散步，那里生长着 $n$ 棵树。他们决定调皮一下，把公园里的树涂上颜色。这些树从左到右编号为 $1$ 到 $n$。 最初，第 $i$ 棵树有颜色 $c_{i}$。ZS the Coder 和 Chris the Baboon 只认识 $m$ 种不同的颜色，所以 $0 \leq c_{i} \leq m$，其中 $c_{i}=0$ 表示第 $i$ 棵树还未上色。 ZS the Coder 和 Chris the Baboon 决定只给未上色的树（即 $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 the Coder 和 Chris the Baboon 想给所有未着色的树涂色，使得最终方案的美丽度恰好为 $k$。他们需要你帮助确定完成该工作的最少油漆用量（升数）。 请注意，已经着色的树不能再重新涂色。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq k \leq n \leq 100$，$1 \leq m \leq 100$），分别表示树的数量、颜色的数量和最终方案的美丽度。 第二行包含 $n$ 个整数 $c_1, c_2, ..., c_n$（$0 \leq c_i \leq m$），表示每棵树初始的颜色。当 $c_i = 0$ 表示第 $i$ 棵树尚未上色，其他情况表示该树已着色，且颜色为 $c_i$。 接下来有 $n$ 行，每行 $m$ 个整数。第 $i$ 行的第 $j$ 个数表示 $p_{i,j}$（$1 \leq p_{i,j} \leq 10^9$），即将第 $i$ 棵树刷成颜色 $j$ 需要的油漆升数。即便是已经着色的树也会给出 $p_{i,j}$，但这些树无法再被重新着色。

输出一个整数，表示完成工作的最少所需油漆。如果不存在美丽度为 $k$ 的合法涂色方案，输出 $-1$。

在第一个样例中，将树分别用颜色 $2,1,1$ 上色时所需油漆最少，总量为 $2+3+5=10$。注意如果全部涂成 $1,1,1$，则美丽度为 $1$（$\{1,1,1\}$ 是唯一的分组），不符合要求。 第二个样例中所有树已经被着色，但美丽度为 $3$，所以不存在合法方案，输出 $-1$。 最后一个样例中所有树已经被着色且美丽度正好为 $k$，所以不需再用油漆，输出 $0$。 由 ChatGPT 5 翻译