Вася играет в LionAge II. Ему надоело играть с глупым компьютером, поэтому он поставил себе эту популярнейшую MMORPG, чтобы сражаться со своими друзьями. Вася придумал имя своему персонажу — непустую строку s, состоящую из маленьких латинских букв. Однако, чтобы не ударить в грязь лицом перед друзьями, Вася решил изменить не более k букв имени персонажа таким образом, чтобы новое имя звучало как можно лучше. Благозвучие строки определяется следующим образом: для каждой пары соседних символов x и y (x находится в строке непосредственно перед y) к результату добавляется бонус c(x, y). Ваша задача определить, какое наибольшее благозвучие можно получить, изменив не более k букв в имени персонажа Васи.