植物大战僵尸

题号：NC219225
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

佬姜家有一片比师大还大的矩形后院。为了抵御僵尸的进攻，佬姜把矩形后院分割为 $n$ 行 $m$ 列的小方格，在每个方格里种植了至多一种奇妙植物。
不过佬姜并不喜欢佬姜家的园丁HPY狂野的种植风格。于是，他希望对现在的后院进行如下修改任意次：

1、铲除一个方格上的植物。该操作耗费 $0$ 。目标方格成为空。

2、在目标为空的方格上种植第 $x$ 种植物。该操作耗费 $cost_x$ 。

佬姜希望使后院的每一列方格成为整齐的。当且仅当一列方格中没有植物，或一列方格中填满了相同的植物时，可称为该列方格是整齐的。同时，为了保证能够抵御僵尸的进攻，佬姜希望修改后的后院的植物数量不少于最初的植物数量。请帮佬姜计算出，要满足佬姜的要求，至少需要耗费多少？

输入描述:

第一行输入三个整数 $n, m, x(1 \leq n, m, x \leq1000)$ ，分别表示佬姜家的后院被划分为n行m列的方格，且有x种植物可供选择。

第二行包括 $x$ 个整数 $cost_1, cost_2, ……, cost_x (1<cost_i<1500)$ ， $cost_i$ 表示种植第 $i$ 种植物的耗费。

接下来 $n$ 行，每行包含 $m$ 个数字， $\begin{bmatrix} p_{1,1} & \dots & p_{1,m}\\ \vdots & \ddots &\vdots \\ p_{n,1} & \dots & p_{n,m} \end{bmatrix} (0 \leq p_{i,j} \leq x)$ 其中 $p_{i,j}$ 表示初始第 $i$ 行第 $j$ 列格子的植物种类。 $p_{i,j} = 0$ 表示初始第 $i$ 行第 $j$ 列格子为空。

输出描述:

输出仅包括一个数字，表示使后院满足佬姜要求的最小耗费。

示例1

输入

复制

5 8 4
50 100 25 50
1 2 0 0 0 0 0 0
0 1 0 2 2 3 0 0
1 1 2 2 4 0 0 0
1 2 0 2 0 0 3 0
1 2 0 2 0 0 0 0

输出

复制

说明

一种可行的耗费为350的方案：

1 0 0 2 0 3 3 0