Problem
Em um dos canais de TV, a próxima loteria é realizada toda semana. Durante a semana, os participantes fazem suas apostas. Cada aposta consiste em nomear algum número de M dígitos no sistema numérico de base K (isto é, de fato, cada participante nomeia M dígitos, cada um dos quais está no intervalo de 0 a K & menos; 1). Zeros à esquerda são permitidos em números.
Em algum momento, as apostas no sorteio atual terminam e, a partir daí, o apresentador anuncia o número vencedor na televisão (este também é um número de M dígitos no sistema de numeração K-ary). Depois disso, os telespectadores, cujo primeiro dígito de seu número coincidiu com o primeiro dígito do número nomeado pelo apresentador, recebem uma vitória no valor de A
1 rublos. Aqueles que acertaram os dois primeiros dígitos de — receba A
2 rublos (ao mesmo tempo, se o jogador tiver o segundo dígito correspondido, mas o primeiro dígito não corresponder, ele não receberá nada). Da mesma forma, aqueles que adivinharam os três primeiros dígitos recebem A
3 rublos. E assim por diante. Aqueles que adivinharam o número inteiro recebem totalmente os rublos Am. Além disso, se o jogador adivinhou os primeiros t dígitos, ele recebe A
t rublos, mas não recebe prêmios por adivinhar t−1, t−2, etc. dígitos. Se o jogador não acertar o primeiro número, ele não ganha nada.
Escreva um programa que, dadas as apostas conhecidas feitas pelos telespectadores, encontre o número que o apresentador de TV deve indicar para que a empresa organizadora pague o valor mínimo como prêmio. Para sua comodidade, as apostas feitas pelos jogadores já estão classificadas em ordem não decrescente.
Entrada
A primeira linha contém os números N (o número de telespectadores que fizeram suas apostas, 1N100000), M (o comprimento dos números 1M10) K (a base do sistema numérico 2 ≤ K ≤ 10). A próxima linha contém M inteiros A
1, A
2, ..., A
M, especificando pagamentos se apenas o primeiro, primeiros dois, ... , todos os dígitos (1 ≤ A
1 ≤ A
2 ≤ ... ≤ A
M ≤ 100000 ) . Cada uma das próximas N linhas contém um número K-ário de M dígitos. Os números estão em ordem não decrescente.
Impressão
Na primeira linha imprima o número desejado (se houver várias soluções — imprima alguma delas) e na segunda linha — o valor que, ao nomear o apresentador de TV no primeiro dia, deverá ser pago a título de vitória.
Exemplos
| # |
Entrada |
Saída |
| 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 |