On one of the TV channels, the next lottery is held every week. During the week, participants make their bets. Each bet consists of naming some M-digit number in the base K number system (that is, in fact, each participant names M digits, each of which lies in the range from 0 to K & minus; 1). Leading zeros are allowed in numbers.
At some point, betting on the current draw ends, and after that, the presenter announces the winning number on television (this is also an M-digit number in the K-ary number system). After that, those TV viewers, whose first digit of their number coincided with the first digit of the number named by the host, receive a win in the amount of A
1 rubles. Those who matched the first two digits of — receive A
2 rubles (at the same time, if the player has the second digit matched, but the first digit did not match, he does not receive anything). Similarly, those who guessed the first three digits receive A
3 rubles. And so on. Those who guessed the whole number fully receive Am rubles. Moreover, if the player guessed the first t digits, then he receives A
t rubles, but does not receive prizes for guessing t−1, t−2, etc. digits. If the player didn't guess the first number, he gets nothing.
Write a program that, given the known bets made by viewers, finds the number that the TV presenter must name in order for the organizing company to pay out the minimum amount as winnings. For your convenience, bets made by players are already sorted in non-descending order.
Input
The first line contains the numbers N (the number of TV viewers who made their bets, 1N100000), M (the length of the numbers 1M10) K (the base of the number system 2 ≤ K ≤ 10). The next line contains M integers A
1, A
2, ..., A
M, specifying payoffs if only the first, first two ,... , all digits (1 ≤ A
1 ≤ A
2 ≤ ... ≤ A
M ≤ 100000 ). Each of the next N lines contains one M-digit K-ary number. The numbers are in non-decreasing order.
Imprint
On the first line print the desired number (if there are several solutions — print any of them), and on the second line — the amount that, when naming the TV presenter on the first day, will have to be paid as a win.
Examples
| # |
Input |
Output |
| 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 |