Coloreando los Árboles
Alex y Chris decidieron colorear los árboles del parque. Los árboles están numerados con números enteros del a de izquierda a derecha. Inicialmente, el árbol tiene color . Alex y Chris reconocen sólo colores diferentes, así que , donde si significa que el árbol no está coloreado.
Alex y Chris deciden colorear sólo los árboles incoloros, es decir, los árboles con . Pueden colorear cada uno de ellos en cualquiera de los colores de a . Colorear el -ésimo árbol con el color requiere exactamente 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 árboles para que cada grupo contenga árboles del mismo color. Por ejemplo, si los colores de los árboles de izquierda a derecha son , la belleza de la coloración es , ya que podemos dividir los árboles en grupos contiguos del mismo color: .
Alex y Chris quieren colorear todos los árboles incoloros para que la belleza de la coloración sea exactamente . 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, , y - el número de árboles, el número de colores y la belleza del colorido resultante, respectivamente.
La segunda línea contiene números enteros , los colores iniciales de los árboles. es igual a si el número del árbol es incoloro, de lo contrario el árbol -ésimo tiene el color .
Luego siguen líneas. Cada una de ellas contiene números enteros. El número -ésimo de la línea -ésima denota - la cantidad de litros que los amigos necesitan para colorear el árbol -ésimo con el color . Los números 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 , imprima .
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