P1140 Similar Genes

Everyone knows that a gene can be regarded as a sequence of base pairs. It contains 4 types of nucleotides, abbreviated as `A, C, G, T`. Biologists are working to discover the functions of human genes in order to diagnose diseases and invent medicines. In a task by a human gene working group, biologists are studying the similarity between two genes, because this research plays an extraordinary role in treating diseases.

The similarity between two genes is computed as follows: For two given genes, for example `AGTGATG` and `GTTAG`, align their bases with each other. Of course, you may insert some gap bases `-` in between, for example: $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|} \hline \tt A & \tt G & \tt T & \tt G & \tt A & \tt T & \texttt - & \tt G \\ \hline \texttt - & \tt G & \tt T & \texttt - & \texttt - & \tt T & \texttt A & \tt G \\ \hline \end{array} $$ Then the similarity between the two genes can be described as the sum of pairwise base similarities, as shown in the following table: $$ \def\arraystretch{1.5} \begin{array}{ |c|c|c|c|c|c|} \hline & \tt A & \tt C & \tt G & \tt T & \texttt - \\ \hline \tt A & 5 & -1 & -2 & -1 & -3\\ \hline \tt C & -1 & 5 & -3 & -2 & -4 \\\hline \tt G & -2 & -3 & 5 & -2 & -2 \\\hline \tt T & -1 & -2 & -2 & 5 & -1 \\\hline \texttt - & -3 & -4 & -2 & -1 & * \\\hline \end{array} $$ Thus the similarity is: $(-3)+5+5+(-2)+(-3)+5+(-3)+5=9$. Since the alignment between two genes is not unique, for example: $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|} \hline \tt A & \tt G & \tt T & \tt G & \tt A & \tt T & \tt G \\ \hline \texttt - & \tt G & \tt T & \texttt T & \texttt A & \texttt - & \tt G \\ \hline \end{array} $$ The similarity is: $(-3)+5+5+(-2)+5+(-1)+5=14$. Define the similarity between two genes as the maximum similarity among all alignments.

There are two lines. Each line first contains an integer $n$, representing the length of the gene sequence; after a space is a gene sequence that contains only the four letters $\verb!A!,\verb!C!,\verb!G!,\verb!T!$. $1 \le n \le 100$.

Only one line: the similarity of the input genes.

Translated by ChatGPT 5