← 返回题目列表

Codeforces · 711/C

C. 着色树

中文机器翻译题面 查看原题

编码员 ZS 和狒狒克里斯已经抵达 Udayland!他们在有n棵树的公园里散步。他们决定顽皮地给公园里的树上色。这些树从左到右用 1 到 n 的整数进行编号。

最初,树 i 的颜色为 ci。编码员 ZS 和狒狒克里斯只能识别 m 种不同的颜色,因此 0 ≤ ci ≤ m,其中 ci = 0 表示树 i 是无色的。

编码员 ZS 和狒狒克里斯决定只为未着色的树(即 ci = 0 的树)着色。他们可以用从 1 到 m 的 m 种颜色中的任意一种为每棵树着色。用颜色 j 给第 i 棵树着色正好需要 pi, 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 和狒狒克里斯想要为所有未着色的树着色,以便着色的美感恰好为 k。他们需要您的帮助来确定完成工作所需的最小油漆量(以升为单位)。

请注意,朋友们不能给已经着色的树着色。

输入

第一行包含三个整数,n、m 和 k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100)——分别是树的数量、颜色的数量和最终着色的美感。

第二行包含 n 个整数 c1, c2, ..., cn (0 ≤ ci ≤ m),即树的初始颜色。如果树编号 i 是未着色的,则 ci 等于 0,否则第 i 棵树的颜色为 ci。

接下来是 n 行。每个都包含 m 个整数。其中第 i 行上的第 j 个数字表示 pi, j (1 ≤ pi, j ≤ 109) - 朋友们用颜色 j 为第 i 棵树着色所需的升数。即使对于最初着色的树也指定了 pi, j,但这样的树仍然无法着色。

输出

打印一个整数,即为树木着色所需的最小油漆量。如果没有美丽 k 的有效树木着色,则打印 - 1。

示例

输入 #1

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

输出 #1

10

输入 #2

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

输出 #2

-1

输入 #3

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

输出 #3

5

输入#4

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

输出#4

0

注意

在第一个示例案例中,用颜色 2, 1, 1 为树木着色可以最大限度地减少所用的油漆量,等于 2 + 3 + 5 = 10。请注意,1, 1, 1 无效,因为这种着色的美观度等于 1({1, 1, 1} 是将树木分组为同一颜色的单个组的一种方法)。

在第二个示例中,所有树木都被着色,但着色的美度为 3,因此没有有效的着色,答案为 - 1。

在最后一个示例中,所有树木都被着色,并且着色的美感与 k 匹配,因此没有使用油漆,答案为 0。