Gene Sequence Similarity Maximization

Given two gene sequences composed of characters A, C, G, and T, you are to calculate the maximum similarity score between them using an alignment method.

The alignment is performed by possibly inserting gaps (-) between characters. The similarity score between two aligned sequences is defined as the sum of the scores for each pair of aligned characters according to the following scoring matrix:

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline & \texttt{A} & \texttt{C} & \texttt{G} & \texttt{T} & \texttt{-} \\ \hline \texttt{A} & 5 & -1 & -2 & -1 & -3\\ \hline \texttt{C} & -1 & 5 & -3 & -2 & -4 \\ \hline \texttt{G} & -2 & -3 & 5 & -2 & -2 \\ \hline \texttt{T} & -1 & -2 & -2 & 5 & -1 \\ \hline \texttt{-} & -3 & -4 & -2 & -1 & \text{*} \\ \hline \end{array} $$

Note that aligning {@literal -} with {@literal -} is not allowed. The overall similarity of two sequences is defined as the maximum possible alignment score achievable by any valid alignment.

Example:

For sequences AGTGATG and GTTAG, one alignment is:

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|} \hline \texttt{A} & \texttt{G} & \texttt{T} & \texttt{G} & \texttt{A} & \texttt{T} & \texttt{-} & \texttt{G} \\ \hline \texttt{-} & \texttt{G} & \texttt{T} & \texttt{-} & \texttt{-} & \texttt{T} & \texttt{A} & \texttt{G} \\ \hline \end{array} $$

which gives a score of 9. Another alignment is:

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|} \hline \texttt{A} & \texttt{G} & \texttt{T} & \texttt{G} & \texttt{A} & \texttt{T} & \texttt{G} \\ \hline \texttt{-} & \texttt{G} & \texttt{T} & \texttt{T} & \texttt{A} & \texttt{-} & \texttt{G} \\ \hline \end{array} $$

with a score of 14. The maximum similarity between the two gene sequences is therefore 14.

inputFormat

The input consists of two lines. The first line is the first gene sequence and the second line is the second gene sequence. Both sequences contain only the characters A, C, G, and T.

outputFormat

Output a single integer representing the maximum similarity score obtained by aligning the two sequences using the given scoring scheme.

sample

AGTGATG
GTTAG

14