Задача 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.
Ведущий лотереи имеет возможность схитрить: не брать выигрышное число
случайно, а подобрать его, зная, какие числа назвал каждый из игроков.
Какую наименьшую сумму выигрышей ему все же придется выплатить?
Технические условия
Программа
Lottery должна прочитать с клавиатуры количество цифр в каждом числе
K, основание системы счисления M, количество игроков N, а далее
N штук K-значных чисел, потом суммы выигрышей
c1, c2 ..., cK. Все входные данные
записаны в одну строку, любые соседние числа («обычные» или в системе
счисления с основанием M) разделены ровно одним пробелом.
Программа должна вывести на экран два числа
через пробел — минимальную сумму, которую все же придется выплатить (ее
выводить в десятичной системе), и выигрышное число, которое подбирает
ведущий (его нужно вывести как K-значное в системе счисления с основанием
M, если нужно — с нулями спереди). Если есть разные выигрышные числа,
при которых нужно выплатить одинаковую минимальную сумму, вывести
меньшее из них.
Пример
Ввод
2 2 5 00 10 01 00
11 7 35
Вывод
42 10