CF73C LionAge II

Vasya plays the LionAge II. He was bored of playing with a stupid computer, so he installed this popular MMORPG, to fight with his friends. Vasya came up with the name of his character — non-empty string $ s $ , consisting of a lowercase Latin letters. However, in order not to put up a front of friends, Vasya has decided to change no more than $ k $ letters of the character name so that the new name sounded as good as possible. Euphony of the line is defined as follows: for each pair of adjacent letters $ x $ and $ y $ ( $ x $ immediately precedes $ y $ ) the bonus $ c(x,y) $ is added to the result. Your task is to determine what the greatest Euphony can be obtained by changing at most $ k $ letters in the name of the Vasya's character.

The first line contains character's name $ s $ and an integer number $ k $ ( $ 0

Output the only number — maximum possible euphony оf the new character's name.

In the first example the most euphony name will be $ looser $ . It is easy to calculate that its euphony is 36.