Problem
En uno de los canales de televisión, la próxima lotería se lleva a cabo cada semana. Durante la semana, los participantes hacen sus apuestas. Cada apuesta consiste en nombrar algún número de M dígitos en el sistema numérico base K (es decir, de hecho, cada participante nombra M dígitos, cada uno de los cuales se encuentra en el rango de 0 a K & menos; 1). Los ceros iniciales están permitidos en los números.
En algún momento, terminan las apuestas en el sorteo actual y, después de eso, el presentador anuncia el número ganador en la televisión (este también es un número de dígito M en el sistema numérico K-ary). Después de eso, los televidentes, cuyo primer dígito de su número coincidió con el primer dígito del número nombrado por el presentador, reciben una ganancia de A
1 rublos. Aquellos que coincidieron con los dos primeros dígitos de — recibe A
2 rublos (al mismo tiempo, si el jugador tiene el segundo dígito coincidente, pero el primer dígito no coincide, no recibe nada). Del mismo modo, aquellos que adivinaron los tres primeros dígitos reciben A
3 rublos. Etcétera. Aquellos que adivinaron el número completo reciben rublos Am. Además, si el jugador acertó los primeros t dígitos, entonces recibe A
t rublos, pero no recibe premios por adivinar t−1, t−2, etc. dígitos Si el jugador no acertó el primer número, no recibe nada.
Escribir un programa que, dadas las apuestas conocidas que realizan los televidentes, encuentre el número que el presentador de televisión debe nombrar para que la empresa organizadora pague la cantidad mínima en concepto de ganancias. Para su comodidad, las apuestas realizadas por los jugadores ya están ordenadas en orden no descendente.
Entrada
La primera línea contiene los números N (el número de televidentes que hicieron sus apuestas, 1N100000), M (la longitud de los números 1M10) K (la base del sistema numérico 2 ≤ K ≤ 10). La siguiente línea contiene M enteros A
1, A
2, ..., A
M, especificando pagos si solo el primero, los dos primeros, ... , todos los dígitos (1 ≤ A
1 ≤ A
2 ≤ ... ≤ A
M ≤ 100000 ) . Cada una de las siguientes N líneas contiene un número K-ario de M dígitos. Los números están en orden no decreciente.
Impresión
En la primera línea, escriba el número deseado (si hay varias soluciones, escriba cualquiera de ellas), y en la segunda línea, escriba; cantidad que, al nombrar al presentador de televisión el primer día, habrá que abonar en concepto de premio.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111 |
011
6 |
| 2 |
1 1 10
100
0 |
1
0 |