Problema C - Apagando Letras

O David e a Cristina adoram jogos lexicais, isto é, jogos envolvendo palavras, tais como palavras cruzadas, sopas de letras ou scrabble. Desta vez estão a brincar com um jogo que consiste em transformar uma palavra numa outra palavra mais pequena, tentando obter pelo caminho a maior pontuação possível, de acordo com as regras do jogo. Neste caso, a única operação permitida no jogo chama-se delete e corresponde a apagar uma letra, sendo que cada delete vale um certo número de pontos. Para transformar uma palavra, os dois amigos podem ir usando sucessivos deletes até chegarem ao resultado pretendido, maximizando o número de pontos.

Imagina por exemplo que as duas palavras em questão são banana e ana. Existem várias maneiras de construir uma sequência de deletes que transforma a primeira palavra na segunda. Duas dessas hipóteses estão exemplificadas a seguir:

banana        banana
banan         bnana
bana          nana
ana           ana

A pontuação de cada delete é a soma da distância entre a letra que está sendo apagada e as duas letras adjacentes. Se a letra for a primeira da palavra, ou a última, só tem uma outra letra adjacente e por isso apenas recebe a pontuação relativa à distância a essa letra. Por definição, a distância entre duas letras, d(c₁,c₂), é o número de letras que é preciso percorrer no alfabeto para chegar de uma letra a outra:

Alfabeto: abcdefghijklmnopqsrtuvwxyz

Exemplos de distâncias:
d(a,a) = 0
d(a,b) = d(b,a) = 1
d(a,z) = d(a,z) = 25
d(c,g) = d(g,c) = 4
d(o,u) = d(u,o) = 6

A pontuação de uma sequência de deletes é, por definição, a soma das pontuações de cada delete. Para os exemplos anteriores, as pontuações seriam as seguintes:

banana 13 -> d(a,n)            banana 14 -> d(a,b)+d(a,n)
banan  13 -> d(n,a)            bnana  12 -> d(b,n)
bana    1 -> d(b,a)            nana   13 -> d(n,a)
ana                            ana

Total: 27 (13+13+1)            Total: 39 (14+12+13)

Transformar uma palavra noutra usando deletes até nem é difícil. Difícil é obter a pontuação maxima! Nota que nenhuma das anteriores sequências de deletes corresponde à pontuação máxima possível, que neste caso é 40. Um exemplo de uma sequência que obtém este número de pontos é:

banana  1 -> d(b,a)
anana  26 -> d(n,a)+d(n,a)
aana   13 -> d(a,a)+d(a,n)
ana

Total: 40 (1+26+13)

Queres ajudar o David e a Cristina a calcular a pontuação máxima?

O Problema

Dadas duas palavras, a tua tarefa é calcular a maior pontuação possível de obter numa sequência de deletes que transforma a primeira palavra na segunda palavra. A pontuação de cada delete é igual à soma das distâncias entre a letra apagada e as duas letras adjacentes, exceto se a letra for a primeira ou a última da palavra, caso onde apenas conta a pontuação relativa à distância à única letra adjacente.

Input

O input é constituído por duas linhas, cada uma delas com uma palavra formada exclusivamente por letras minúsculas.

Output

O output deve ser constituído por uma única linha indicando qual a melhor pontuação que se pode obter para transformar a palavra da 1ª linha na palavra da 2ª linha usando uma sequência de deletes, tal como atrás foi descrito. É garantido que existe sempre pelo menos uma maneira de transformar a primeira palavra na segunda.

Restrições

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que T₁ e T₂ são menores ou iguais a 10.

Para um conjunto de casos de teste valendo 30% dos pontos, acontece sempre que T₂=1 e T₁ é maior que 10.

Exemplo de Input 1

banana
ana

Exemplo de Output 1

40

Exemplo de Input 2

david
d

Exemplo de Output 2

78