Задача Lottery
Є лотерея, що проводиться за
правилами: грають N (2 ≤ N ≤ 500 000) осіб, кожен гравець називає
будь-яке K-значне (2 ≤ K ≤ 17) число в системі числення з
основою M (2 ≤ M ≤ 10). Усі числа порівнюються з виграшним числом,
і ті гравці, числа яких співпали з виграшним лише у 1-ій цифрі,
отримують виграш c1; у 1-ій та 2-ій —
c2 (причому не додатково до c1, а
замість c1), у 1-ій, 2-ій та 3-ій
— c3 і т.д. Гарантовано, що 1 ≤ c1 ≤ c2 ≤ … ≤ cK
≤ 4000. Вгадані цифри повинні починатися з 1-ої і йти підряд (зокрема,
якщо не вгадана 1-а цифра, виграшу не буде незалежно від кількості
подальших вгаданих ). Числа, що їх називають гравці, а також виграшне
число, можуть починатися з нулів.
Ведучий лотереї має можливість схитрувати: не брати
виграшне число випадково, а підібрати його, знаючи, які числа назвав
кожен із гравців. Яку найменшу суму виграшів йому все ж доведеться
виплатити?
Технічні умови
Програма Lottery читає з клавіатури кількість цифр у
кожному числі K, основу системи числення M, кількість
гравців N, а далі N штук K-цифрових чисел, потім
суми виграшів c1, c2, ..., cK.
Усі вхідні дані записані в один рядок, будь-які сусідні числа («звичайні»
чи в системі числення з основою M) розділені рівно одним
пропуском.
Програма виводить на екран два числа, розділені одним
пропуском —мінімальну суму, яку все ж доведеться виплатити (її виводити
у десятковій системі), та виграшне число, яке підбирає ведучий (його
треба вивести як K-цифрове в системі числення з основою M,
у разі потреби — з нулями спереду). Якщо є різні виграшні числа, при
яких треба виплатити однакову мінімальну суму, вивести найменше з них.
Приклад
Введення
2 2 5 00 10 01 00
11 7 35
Виведення
42 10