题目描述

在一个小城市里，有 $m$ 个房子排成一排，你需要给每个房子涂上 $n$ 种颜色之一（颜色编号为 $1$ 到 $n$ ）。有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色。

我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 $houses = [1,2,2,3,3,2,1,1]$ ，它包含 5 个街区 $[{1}, {2,2}, {3,3}, {2}, {1,1}]$ 。）

给你一个数组 $houses$ ，一个 $m * n$ 的矩阵 $cost$ 和一个整数 $target$ ，其中：

• $houses[i]$：是第 $i$ 个房子的颜色， 0  表示这个房子还没有被涂色。
• $cost[i][j]$：是将第 $i$ 个房子涂成颜色 $j+1$ 的花费。

请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 $target$ 个街区。如果没有可用的涂色方案，请返回  -1  。

输入格式

第一行三个空格隔开的整数表示 $m,n,target$；

第二行 $m$ 个空格隔开的非负整数表示数组 $houses$ 中的各个元素；

接下来的 $m$ 行，每行 $n$ 个空格隔开的整数表示 $cost[i]$ 中的各个元素。

输出格式

一行一个整数表示答案。

示例 1：

5 2 3
0 0 0 0 0
1 10
10 1
10 1
1 10
5 1

9

解释: 房子涂色方案为 [1,2,2,1,1] 此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。 涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。

示例 2：

5 2 3
0 2 1 2 0
1 10
10 1
10 1
1 10
5 1

11

解释: 有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2] 此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。 给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。

示例 3：

5 2 5
0 0 0 0 0
1 10
10 1
1 10
10 1
1 10

5

示例 4：

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

-1

解释: 房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。

提示：

• $m == houses.length == cost.length$
• $n == cost[i].length$
• $1 <= m <= 100$
• $1 <= n <= 20$
• $1 <= target <= m$
• $0 <= houses[i] <= n$
• $1 <= cost[i][j] <= 10^4$

SOURCE

粉刷房子 III