Problem
Su uno dei canali TV, ogni settimana si tiene la prossima lotteria. Durante la settimana, i partecipanti fanno le loro scommesse. Ogni scommessa consiste nel nominare un numero di M cifre nel sistema numerico di base K (ovvero, in effetti, ogni partecipante nomina M cifre, ciascuna delle quali si trova nell'intervallo da 0 a K & meno; 1). Gli zeri iniziali sono consentiti nei numeri.
Ad un certo punto, le scommesse sull'attuale estrazione terminano, dopodiché il presentatore annuncia il numero vincente in televisione (questo è anche un numero di cifre M nel sistema numerico K-ary). Successivamente, quei telespettatori la cui prima cifra del loro numero coincideva con la prima cifra del numero indicato dal presentatore, ricevono una vincita di A
1 rubli. Coloro che corrispondono alle prime due cifre di — ricevere A
2 rubli (allo stesso tempo, se il giocatore ha la seconda cifra abbinata, ma la prima cifra non corrisponde, non riceve nulla). Allo stesso modo, coloro che hanno indovinato le prime tre cifre ricevono A
3 rubli. E così via. Coloro che hanno indovinato l'intero numero ricevono completamente Am rubli. Inoltre, se il giocatore ha indovinato le prime t cifre, riceve A
t rubli, ma non riceve premi per aver indovinato t−1, t−2, ecc. cifre. Se il giocatore non ha indovinato il primo numero, non ottiene nulla.
Scrivete un programma che, viste le puntate note fatte dai telespettatori, trovi il numero che il presentatore televisivo deve nominare affinché la società organizzatrice possa sborsare l'importo minimo come vincita. Per tua comodità, le scommesse effettuate dai giocatori sono già ordinate in ordine non decrescente.
Inserimento
La prima riga contiene i numeri N (il numero di telespettatori che hanno fatto le loro scommesse, 1N100000), M (la lunghezza dei numeri 1M10) K (la base del sistema numerico 2 ≤ K ≤ 10). La riga successiva contiene M interi A
1, A
2, ..., A
M, specificando i guadagni se solo il primo, i primi due , ... , tutte le cifre (1 ≤ A
1 ≤ A
2 ≤ ... ≤ A
M ≤ 100000 ) . Ognuna delle N righe successive contiene un numero K-ario di M cifre. I numeri sono in ordine non decrescente.
Impressum
Sulla prima riga stampa il numero desiderato (se ci sono più soluzioni — stampane una qualsiasi), e sulla seconda riga — l'importo che, quando si nomina il presentatore televisivo il primo giorno, dovrà essere pagato come vincita.
Esempi
| # |
Input |
Uscita |
| 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 |