Description

$\operatorname{DNA}$ molecules are carriers of human genetic information, indirectly guiding protein synthesis. A $\operatorname{DNA}$ molecule is a long chain composed of four nucleotides: adenine nucleotide (denoted by $\operatorname{A}$), guanine nucleotide (denoted by $\operatorname{G}$), cytosine nucleotide (denoted by $\operatorname{C}$), and thymine nucleotide (denoted by $\operatorname{T}$). By convention, a $\{\operatorname{A,T,C,G}\}$-alphabet string is used to represent a $\operatorname{DNA}$ sequence, such as $\operatorname{CGTTAGA}$.

During biological evolution, $\operatorname{DNA}$ molecules may undergo various mutations. These mutations change genetic information, enabling species differentiation and forming biological diversity.

There are three main types of mutations:

1. Inserting a new nucleotide into a $\operatorname{DNA}$ sequence,
2. Deleting a nucleotide from a $\operatorname{DNA}$ sequence,
3. Substituting one nucleotide in the $\operatorname{DNA}$ sequence with another.

An alignment of two $\operatorname{DNA}$ sequences is an arrangement that places the two sequences so that identical nucleotides appear at the same positions. If the nucleotides at the same position differ, that difference is attributed to one of the three types of mutations. For example, for two $\operatorname{DNA}$ sequences $T_1 =\operatorname{ATCAG}$, $T_2 =\operatorname{ACTAG}$, one possible alignment is as follows (where $-$ denotes a gap):

Alignment 1:

Another possible alignment is:

Alignment 2:

The more identical nucleotide pairs the two $\operatorname{DNA}$ sequences have at the same positions, the more similar they are, indicating functional similarity and phylogenetic relatedness.

The scoring rules for an alignment of two $\operatorname{DNA}$ sequences are as follows:

1. If the nucleotides at the same position are identical, score $1$ point.
2. If the nucleotides at the same position are different, score $0$ points.
3. If one sequence has a nucleotide at some position while the other has $-$ at that position, score $-2$ points.

For example, the score of Alignment 1 is $0$ points, and the score of Alignment 2 is $3$ points.

The task is: Given two $\operatorname{DNA}$ sequences, find an alignment that maximizes the score.

Input Format

The input consists of two lines.

The first line is the $\text{DNA}$ sequence $T _ 1$, and the second line is the $\text{DNA}$ sequence $T _ 2$. The length of each sequence does not exceed $1000$. The letters in the sequences are lowercase or uppercase English letters.

Output Format

Output the maximum score found.

Atcag
Actag

3

Hint

Translated by ChatGPT 5