Coloreando los Árboles


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Alex y Chris decidieron colorear los árboles del parque. Los árboles están numerados con números enteros del 1 a N de izquierda a derecha. Inicialmente, el árbol i tiene color c_i. Alex y Chris reconocen sólo M colores diferentes, así que 0 \le c_i \le M, donde si c_i = 0 significa que el árbol i no está coloreado.

Alex y Chris deciden colorear sólo los árboles incoloros, es decir, los árboles con c_i = 0. Pueden colorear cada uno de ellos en cualquiera de los M colores de 1 a M. Colorear el i-ésimo árbol con el color j requiere exactamente p_{i, j} litros de pintura.

Los dos amigos definen la belleza de una coloración de los árboles como el número mínimo de grupos contiguos (cada grupo contiene algún subsegmento de árboles) en los que se pueden dividir todos los N árboles para que cada grupo contenga árboles del mismo color. Por ejemplo, si los colores de los árboles de izquierda a derecha son 2, 1, 1, 1, 3, 2, 2, 3, 1, 3, la belleza de la coloración es 7, ya que podemos dividir los árboles en 7 grupos contiguos del mismo color: \{2\}, \{1, 1, 1\}, \{3\}, \{2, 2\}, \{3\}, \{1\}, \{3\}.

Alex y Chris quieren colorear todos los árboles incoloros para que la belleza de la coloración sea exactamente K. Necesitan su ayuda para determinar la cantidad mínima de pintura (en litros) necesaria para terminar el trabajo.

Entrada

La primera línea contiene tres números enteros, N, M y K (1 \le K \le N \le 100, 1 \le M \le 100) - el número de árboles, el número de colores y la belleza del colorido resultante, respectivamente.

La segunda línea contiene N números enteros c_1, c_2, ..., c_n (0 \le c_i \le M), los colores iniciales de los árboles. c_i es igual a 0 si el número del árbol i es incoloro, de lo contrario el árbol i-ésimo tiene el color c_i.

Luego siguen N líneas. Cada una de ellas contiene M números enteros. El número j-ésimo de la línea i-ésima denota p_{i, j} (1 \le p_{i, j} \le 10^9) - la cantidad de litros que los amigos necesitan para colorear el árbol i-ésimo con el color j. Los números p_{i, j} se especifican incluso para los árboles de color inicial, pero tales árboles todavía no pueden ser coloreados.

Salida

Imprima un solo entero, la cantidad mínima de pintura necesaria para colorear los árboles. Si no hay coloreos válidos de belleza K, imprima -1.

Ejemplo de Entrada #1

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

Ejemplo de Salida #1

10

Ejemplo de Entrada #2

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

Ejemplo de Salida #2

-1

Comments

There are no comments at the moment.