Description

Xiao A has been looking for his own father recently. How? By DNA matching.

Xiao A has his own method for comparing DNA sequences. The goal is to maximize the similarity score between two DNA sequences. The steps are as follows:

1. Given two DNA sequences, the first of length $n$ and the second of length $m$.
2. Insert any number of gaps at any positions in the two sequences so that the two strings have the same length.
3. Match position by position. If at a position neither character is a gap, let the first be $x$ and the second be $y$, then their similarity is defined as $d(x, y)$. For any maximal contiguous block of gaps of length $k$ in either sequence, we define its similarity as $g(k) = -A - B(k-1)$.

The final similarity score of the two sequences is the sum of all $d(x, y)$ values plus the similarity of all maximal gap blocks.

Now Xiao A has, by some mysterious means, obtained a segment of Xiao B’s DNA sequence. He asks you to compute the maximum similarity score between Xiao A’s DNA sequence and Xiao B’s DNA sequence.

Input Format

The first line contains a string representing Xiao A’s DNA sequence. The second line contains a string representing Xiao B’s DNA sequence. The next $4$ lines each contain $4$ integers separated by spaces, representing the $d$ array in the following order.

d(A,A) d(A,T) d(A,G) d(A,C)
d(T,A) d(T,T) d(T,G) d(T,C)
d(G,A) d(G,T) d(G,G) d(G,C)
d(C,A) d(C,T) d(C,G) d(C,C)

The last line contains two positive integers $A, B$ separated by spaces, as described above.

Output Format

Output a single line: the maximum similarity score of the two sequences.

ATGG
ATCC
5 -4 -4 -4 
-4 5 -4 -4 
-4 -4 5 -4 
-4 -4 -4 5 
2 1

4

Hint

Sample explanation.

First, pad the sequences as follows (“-” denotes a gap):

ATGG--
AT--CC

Then the sum of all $d(x, y)$ is $d(A, A) + d(T, T) = 10$. The sum of the similarity of all maximal contiguous gap blocks is $g(2) + g(2) = -6$. The total is $4$, which can be verified to be the maximum similarity.

For all test points, $0 < B < A \le 1000$, $-1000 \le d(x, y) \le 1000$, $d(x, y) = d(y, x)$, and each sequence contains only the four characters $\{A, T, G, C\}$.

From CodePlus 2017 November Contest, proudly presented by the Student Algorithm and Competition Association, Department of Computer Science and Technology, Tsinghua University.

Credit: Idea/Lu Zhengrong; Problem setter/Lu Zhengrong; Tester/He Haotian.

Git Repo: https://git.thusaac.org/publish/CodePlus201711

Thanks to Tencent for supporting this contest.

Translated by ChatGPT 5