Московская олимпиада по информатике

на сайте www.olympiads.ru

Московская городская олимпиада школьников по информатике, 2005/06 учебный год
при поддержке компании

Задача J. Лотерея

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K-1). Ведущие нули в числах допускаются.

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A₁ рублей. Те, у кого совпали первые две цифры числа - получают A₂ рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A₃ рублей. И так далее. Угадавшие все число полностью получают A_M рублей. При этом если игрок угадал t первых цифр, то он получает A_t рублей, но не получает призы за угадывание t-1, t-2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

Напишите программу, которая по известным ставкам, сделанным телезрителями, находит число, которое должна назвать телеведущая, чтобы фирма-организатор розыгрыша выплатила в качестве выигрышей минимальную сумму. Для вашего удобства ставки, сделанные игроками, уже упорядочены по неубыванию.

Формат входных данных

В первой строке задаются числа N (количество телезрителей, сделавших свои ставки, 1≤N≤100000), M (длина чисел 1≤M≤10) и K (основание системы счисления 2≤K≤10). В следующей строке записаны M чисел A₁, A₂, ..., A_M, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1≤A₁≤A₂≤...≤A_M≤100000). В каждой из следующих N строк записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.

Формат выходных данных

В первой строке выведите искомое число (если решений несколько - выведите любое из них), а во второй строке - сумму, которую при назывании телеведущей первого числа придется выплатить в качестве выигрыша.

Примеры

10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111

011
6

1 1 10
100
0

7
0