Subseqüència comuna valuosa P86300

Una subseqüència d’una paraula p és qualsevol paraula resultat d’esborrar diversos (potser zero) caràcters de p tot respectant l’ordre relatiu dels caràcters que queden.

Teniu dues paraules s i t, formades només amb lletres minúscules. Considereu totes les subseqüències comunes entre s i t sense lletres adjacents iguals. Per exemple, si s =“basat” i t = “tapat”, les úniques candidates són la paraula buida, “a”, “t” i “at”.

Suposeu que cada lletra individual de les dues paraules té un valor associat. Calculeu el valor màxim possible de totes les subseqüències comunes entre s i t sense lletres adjacents iguals. El valor d’una subseqüència és la suma del valor de cada lletra triada, definida com el màxim del valor de la lletra a s i a t.

Entrada

L’entrada consisteix en diversos casos, cadascun amb la paraula s, els valors d’esquerra a dreta de cada lletra d’s, la paraula t, i els valors d’esquerra a dreta de cada lletra de t. Tant s com t tenen entre 1 i 100 lletres minúscules, i tots els valors estan entre 1 i 10⁷.

Sortida

Per a cada cas, escriviu el màxim valor possible.