DNA Sequence Alignment

Little A has been searching for his father using DNA comparison. He has devised his own method of comparing two DNA sequences. Given two DNA sequences – the first of length \(n\) and the second of length \(m\) – you are allowed to insert any number of spaces at any positions in both sequences so that the two resulting strings have equal length. Then, the strings are compared position by position.

If, at a given position, both sequences have a nucleotide (i.e. not a space), and if these characters are \(x\) and \(y\) respectively, the similarity contribution is given by \(d(x,y)\):

• \(d(x,y)=10\) if \(x=y\) (a match)
• \(d(x,y)=-5\) if \(x\neq y\) (a mismatch)

For any maximal consecutive gap segment (i.e. a contiguous block of spaces in one of the sequences) of length \(k\), the gap penalty is defined as:

[ g(k) = -A - B\times (k-1), \quad k\ge 1, ]

The overall similarity between the two sequences is the sum of the \(d(x,y)\) contributions for all positions where both sequences have nucleotides plus the sum of gap penalties for all maximal gap segments. Your task is to compute the maximum possible similarity achievable between Little A's DNA sequence and Little B's DNA sequence using this method.

Note: You are allowed to insert spaces arbitrarily in both sequences. The order of characters in each sequence cannot be changed.

inputFormat

The input consists of three lines:

1. The first line contains four integers \(n\), \(m\), \(A\), and \(B\) where \(n\) and \(m\) denote the lengths of the two DNA sequences, and \(A\) and \(B\) are the gap penalty parameters.
2. The second line contains a string of length \(n\) representing the first DNA sequence. It consists only of the characters A, C, G, and T.
3. The third line contains a string of length \(m\) representing the second DNA sequence. It also consists only of the characters A, C, G, and T.

outputFormat

Output a single integer which is the maximum similarity score achievable after optimally inserting spaces in the two sequences.

sample

4 4 5 2
ACGT
ACGT

40