На одному з телеканалів щотижня проводиться наступна лотерея. Упродовж тижня учасники роблять свої ставки. Кожна ставка полягає в називанні будь-якого \(𝑀\) -значного числа в системі числення з основою \(𝐾\) (тобто, по суті, кожен учасник називає \(𝑀\) цифр, кожна з яких лежить в діапазоні від 0 до \(𝐾−1\)). Провідні нулі у числах допускаються.

У деякий момент прийом ставок на поточний розіграш завершується, і після цього ведучий в телеефірі називає число, що виграло (це також \(M\)-значне число в \(K\)-ій системі числення). Після цього ті телеглядачі, у кого перша цифра їхнього числа збіглася з першою цифрою числа, названого ведучим, одержують виграш у розмірі \(A_1\) грн. Ті, у кого збіглися перші дві цифри числа - отримують \(A_2\) грн (при цьому якщо у гравця збіглася друга цифра, але не збіглася перша, він не отримує нічого). Аналогічно перші три цифри, що вгадали, отримують \(𝐴_3\) грн. І так далі. Ті, що вгадали все число, повністю отримують \(𝐴_M\) грн. При цьому якщо гравець вгадав \(t\) перших цифр, то він отримує \(A_t\) грн, але не отримує призи за вгадування \(t-1, t-2\) і т.д. цифр. Якщо гравець не вгадав першої цифри, він не отримує нічого.

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

Для вашої зручності ставки, зроблені гравцями, вже впорядковані по неспаданю.

Формат вхідних даних

У першому рядку задаються числа \(𝑁\) (кількість телеглядачів, які зробили свої ставки, \(1≤𝑁≤100000\)), \(𝑀\) (довжина чисел \(1≤𝑀≤10\)), \(𝐾\) (основа системи числення \(2≤𝐾≤10\)).

У наступному рядку записані \(𝑀\) чисел \(𝐴_1 , 𝐴_2 , ..., 𝐴_𝑀\) , що задають виграші у разі збігу тільки першої, перших двох,... , всіх цифр (\(1≤𝐴_1≤𝐴_2≤...≤𝐴_𝑀≤1000\)

У кожному з наступних \(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

Приклад вихідних даних

1
0