題目描述

在大三巴一次考古發掘中，發現了一批重要的基因。一個專注於人類基因的研究小組相當關切這些重要的發現，他們要用科學計算的方法把這批基因與現今的人類基因作比對，以便在疾病診斷和藥物開發中加以應用。

基因可以視為一種碱基對序列，由四種核苷酸組成，分別是A、C、G和T。以AGTGATG和GTTAG為例，首先將它們的碱基進行逐一對應。在此過程中，可以插入空碱基-，例如：

A	G	T	G	A	T	-	G
-	G	T	-	-	T	A	G

這樣,兩個基因之間的相似度就可以用堿基之間相似度的總和來描述，堿基之間的相似度如下表所示：

那麼相似度就是：(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。因為兩個基因的對應方法不唯一，例如又有：

A	G	T	G	A	T	G
-	G	T	T	A	-	G

相似度為：(-3)+5+5+(-2)+5+(-1)+5=14。規定兩個基因的相似度為所有對應方法中，相似度最大的那個。

輸入格式

共兩行。每行首先是一個整數，表示基因的長度；隔一個空格後是一個基因序列，序列中只含A,C,G,T四個字母。1<=序列的長度<=100。

僅一行，即輸入基因的相似度。

7 AGTGATG
5 GTTAG