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^7$.

Sortida

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