Задача 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
 

© LIKT 1998-2018