编码员 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。