Alignment 是生物序列（如 DNA 與蛋白質）分析的重要問題。輸入兩個字元序列，我們要將兩序列的字母依照原順序做一個對應，過程中可以將任一序列的某些位置加入空白。

以輸入 CTTAACT 與 CGGATCAT 為例，以下是一個可能的 alignment（以 - 表示空白）：

CTTAAC-T
CGGATCAT

以下也是一個可能的 alignment：

C---TTAACT
CGGATCA--T

alignment 的目的是要評估兩序列有多相似，我們會有一個評分機制。以下是一個例子：

• 兩字母相同得 \(8\) 分
• 相異得 \(-5\) 分
• 字母與空白對應得 \(-3\) 分

給定評分機制並輸入兩序列，我們要計算 最大的 alignment 分數。

Alignment 可分為 global alignment（輸入的序列整個要納入 alignment）與 local alignment（兩序列各選取連續的一段，長度可為 \(0\)，來做 alignment）。

輸入兩字串，計算 local alignment 的最大分數。

輸入格式

第一行與第二行個有一個字串， 字串均只由 \(ATCG\) 四個字母組成， 長度不超過 \(500\)。

輸出格式

Local alignment 的最大分數。

範例輸入 1

ATATCTTAACTGG
CGCGGATCATAA

範例輸出 1

43

範例輸入 2

AAAACTGAGGG
GGCTATT

範例輸出 2

21