[Nikich]

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

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A1 рублей. Те, у кого совпали первые две цифры числа — получают A2 рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A3 рублей. И так далее. Угадавшие все число полностью получают AM рублей. При этом если игрок угадал t первых цифр, то он получает At рублей, но не получает призы за угадывание t–1, t–2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

Входные данные

В первой строке входного файла INPUT.TXT задаются числа N (количество телезрителей, сделавших свои ставки, 1<=N<=100000), M (длина чисел 1<=M<=10) и K (основание системы счисления 2<=K<=10). В следующей строке записаны M чисел A1, A2, …, AM, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1<=A1<=A2<=…<=AM<=100000). В каждой из следующих N строк либо в одной строке через пробел записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.

Выходные данные

В выходной файл OUTPUT.TXT выведите наименьшую сумму, которую придется выплатить в качестве выигрыша


есть идеи? на ум приходит только обычное дерево, что вряд ли выдержит по скорости.