Борис очень любит числа и у него даже есть небольшой магазин интересных чисел. В продаже у него есть n десятичных чисел Bi. Стоимость числа в его магазине равна сумме стоимостей цифр, из которых оно состоит. Заданы значения cd, где cd — стоимость цифры d. Естественно, Борис заинтересован в том, чтобы в его магазине были числа как можно большей стоимости.
Недавно Борису попал в руки магический артефакт A, который может позволить ему увеличить стоимость коллекции. Артефакт представляет собой строку, состоящую из цифр и символов '?'. Чтобы применить артефакт, Борис должен заменить все символы '?' на цифры так, чтобы получилась запись десятичного числа без ведущих нулей (число 0 также запрещено). После этого полученное число прибавится к каждому из чисел Bi, которые есть в коллекции Бориса. Артефакт можно использовать только один раз.
Какую максимальную суммарную стоимость коллекции может получить Борис после применения артефакта?
Выходные данные
Выведите одно целое число — максимальную возможную суммарную стоимость коллекции после применения артефакта.
Примечание
Во втором примере оптимальным выбором будет составить из артефакта число 453. После прибавления этого числа у Бориса окажутся числа 2656, 5682, 729 и 6696. Суммарная стоимость всех цифр в этих числах равна 18 + 15 + 11 + 18 = 62.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
42
3
89
1
958
0 0 1 1 2 2 3 3 4 4
|
4
|
|
2
|
?5?
4
2203
5229
276
6243
2 1 6 1 1 2 5 2 2 3
|
62
|