本题没有可用的提交语言。

Gnaileux Iew 最近对生物信息学产生了兴趣。他日以继夜地阅读论文，全身心投入学习。今天，他准备回顾生物信息学中的基本问题：DNA序列比对。他的目标是找到一个简单而有效的算法，用于对两个高度相似的DNA序列进行全局比对。

DNA序列由一系列字符表示，字符可能是'A'、'G'、'C'或'T'。为了比对两个DNA序列，可以在序列中插入一些空位，使得两个序列长度相同。然后，通过一个得分矩阵计算每一对匹配字符的得分。Gnaileux Iew 使用了一个最小化得分矩阵，因此比对的总得分应尽可能小。以下是Gnaileux Iew使用的得分矩阵：

例如，比对DNA序列 "AAGACG" 和 "CAGAGCTC" 可能如下：

-AAGA-C-G
CA-GAGCTC

总得分为 $3+0+3+0+0+3+0+3+4=16$。

Gnaileux Iew 只对高度相似的序列比对感兴趣。严格来说，满足 $|LCS(A,B)| \times 2 / (|A| + |B|) \geq 90\%$，其中 $A$ 和 $B$ 是需要比对的两个序列，$LCS(A,B)$ 是 $A$ 和 $B$ 的最长公共子序列的长度。

输入格式

输入包含多个测试用例。每个测试用例包含两行，分别是要比对的两个DNA序列。DNA序列仅包含字符 'A'、'G'、'C' 和 'T'。每个序列的长度不超过 50000。

可以假设所有输入用例均为高度相似的序列。

输出格式

对于每个测试用例，输出一行，表示比对的最小总得分。

样例输入 1

AGTGCTGAAAGTTGCGCCAGTGAC
AGTGCTGAAGTTCGCCAGTTGACG
CACAATTTTTCCCAGAGAGA
CGAATTTTTCCCAGAGAGA

样例输出 1

12
7