P4059 [Code+#1] 找爸爸

小 A 最近一直在找自己的爸爸，用什么办法呢，就是 DNA 比对。 小 A 有一套自己的 DNA 序列比较方法，其最终目标是最大化两个 DNA 序列的相似程度，具体步骤如下： 1. 给出两个 DNA 序列，第一个长度为 $n$，第二个长度为 $m$。 2. 在两个序列的任意位置插入任意多的空格，使得两个字符串长度相同 3. 逐位进行匹配，**如果两个序列相同位置上的字符都不是空格**，假设第一个是 $x$，第二个是 $y$，那么他们的相似程度由 $d(x,y)$ 定义。对于两个序列中任意一段极长的长度为 $k$ 的连续空格，我们定义这段空格的相似程度为 $g(k)=-A-B(k-1)$。 那么最终两个序列的相似程度就是所有的 $d(x,y)$ 加上所有的极长空格段的相似程度之和。 现在小 A 通过某种奥妙重重的方式得到了小 B 的 DNA 序列中的一段，他想请你帮他算一下小 A 的 DNA 序列和小 B 的 DNA 序列的最大相似程度。

无

无

### 样例解释 首先，将序列补成如下形式（"-"代表空格） ```cpp ATGG-- AT--CC ``` 然后所有 $d(x,y)$ 的和为 $d(A,A)+d(T,T)=10$ 所有极长连续空格段的相似程度之和为 $g(2)+g(2)=-6$ 总和为 $4$，可以验证，这是相似程度最大的情况。 对于所有测试点，有 $0< B