DZY коллекционирует строки, состоящие только из строчных английских букв. Для каждой строчной буквы c DZY определил значение wc. Для каждой строки s = s1s2... s|s| (|s| — длина строки) ее значение определяется функцией f(s), где
У DZY есть строка s. Он хочет вставить k строчных букв в эту строку так, чтобы значение получившейся строки было как можно больше. Какое максимальное значение он сможет получить?
Выходные данные
Выведите единственное целое число — максимальное значение строки, которое DZY сможет получить.
Примечание
В тестовом примере можно получить строку «abcbbc», тогда значение равно 1·1 + 2·2 + 3·2 + 4·2 + 5·2 + 6·2 = 41.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abc
3
1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
|
41
|