题目描述

有 $n$ 棵树，$m$ 种颜料，要求现在要给这些树涂上颜料，最后涂成 $k$ 段（连续颜色相同划为一段如 $2 , 1 , 1 , 1 , 3 , 2 , 2 , 3 , 1 , 3$ 是 $7$ 段），有些树已经涂了，则不涂了只能涂一次。

给出每棵树的颜色 $c_i$（$0\sim m$），$0$ 表示还没有涂，$1\sim m$ 表示已经涂了哪种颜料。

现在要把所有树都涂上颜料涂成 $k$ 段，求最少要用的颜料量。

输入格式

第一行三个整数 $n,m,k$，$1\le k\le n\le 100$，$1\le m\le 100$。

第二行包含 $n$ 个整数 $c_i$。

接下来输入 $n$ 行 $m$ 列的矩阵元素 $p_{i,j}$，表示把第 $i$ 棵树涂成第 $j$ 种颜色所要的颜料量，$p_{i,j}\le 10^9$。

输出格式

输出一个整数表示答案，如果无解，则输出 $-1$。

3 2 2
0 0 0
1 2
3 4
5 6

10

3 2 2
2 1 2
1 3
2 4
3 5

-1

3 2 2
2 0 0
1 3
2 4
3 5

5

3 2 3
2 1 2
1 3
2 4
3 5

0