Module: Bor

Problem

Sur l'une des chaînes de télévision, la prochaine loterie a lieu chaque semaine. Pendant la semaine, les participants font leurs paris. Chaque pari consiste à nommer un numéro à M chiffres dans le système de numération de base K (c'est-à-dire, en fait, chaque participant nomme M chiffres, dont chacun se situe dans la plage de 0 à K & moins; 1). Les zéros non significatifs sont autorisés dans les nombres.

À un moment donné, les paris sur le tirage en cours se terminent, et après cela, le présentateur annonce le numéro gagnant à la télévision (il s'agit également d'un numéro à chiffres M dans le système de numérotation K-ary). Après cela, les téléspectateurs, dont le premier chiffre de leur numéro coïncide avec le premier chiffre du numéro nommé par l'hôte, reçoivent un gain d'un montant de A₁ roubles. Ceux qui correspondaient aux deux premiers chiffres de — recevez A₂ roubles (en même temps, si le joueur a le deuxième chiffre correspondant, mais que le premier chiffre ne correspond pas, il ne reçoit rien). De même, ceux qui ont deviné les trois premiers chiffres reçoivent A₃ roubles. Et ainsi de suite. Ceux qui ont deviné le nombre entier reçoivent entièrement les roubles Am. De plus, si le joueur a deviné les t premiers chiffres, il reçoit A_t roubles, mais ne reçoit pas de prix pour avoir deviné t−1, t−2, etc. chiffres. Si le joueur n'a pas deviné le premier chiffre, il n'obtient rien.

Écrivez un programme qui, compte tenu des paris connus effectués par les téléspectateurs, trouve le numéro que le présentateur de télévision doit nommer pour que la société organisatrice verse le montant minimum en tant que gains. Pour votre commodité, les paris effectués par les joueurs sont déjà triés par ordre non décroissant.

Entrée
La première ligne contient les nombres N (le nombre de téléspectateurs qui ont fait leurs paris, 1N100000), M (la longueur des nombres 1M10) K (la base du système de numération 2 ≤ K ≤ 10). La ligne suivante contient M entiers A₁, A₂, ..., A_M, spécifiant les gains si seulement le premier, les deux premiers , ... , tous les chiffres (1 ≤ A₁ ≤ A₂ ≤ ... ≤ A_M ≤ 100000 ) . Chacune des N lignes suivantes contient un nombre K-aire à M chiffres. Les nombres sont en ordre non décroissant.

Mentions légales
Sur la première ligne, imprimez le numéro souhaité (s'il y a plusieurs solutions — imprimez l'une d'entre elles), et sur la deuxième ligne — le montant qui, lors de la désignation du présentateur de télévision le premier jour, devra être payé en tant que gain.

Exemples

#	Entrée	Sortie
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