在溫水和彥的家中有一卷失傳已久的古籍。可惜的是，這部古籍因年代久遠，字跡變得模糊不清，有些字甚至已經掉落或錯位。身為永不敗北的男角，你的任務是將古籍修復成原本的模樣（目標字串），讓後人能夠再度欣賞這段珍貴的文化。

在修復過程中，你可以進行以下三種操作來修改字串使古籍內容更接近目標字串：

1. 新增一個字母。
2. 刪除一個字母。
3. 替換一個字母。

但因為打字機效能有限，溫水希望能用最少的操作來達成目的。你能幫他找到修復這些字串最少需要幾次操作嗎？

輸入格式

第一行包含 \(n\) 個由大寫字母(A-Z)的字串，表示待修復古籍字串。
第二行包含 \(m\) 個由大寫字母(A-Z)的字串，表示目標字串。

• \(1 \le n,m \le 5000\)

輸出格式

輸出一個整數，代表修復所需的最少步驟數。

範例輸入

LOVE
MOVIE

範例輸出

2

說明

對於範例測資來說，可以先將 \(LOVE\) 中的 \(L\) 換成 \(M\)（執行一次操作 \(2\)），之後在最尾端新增一個字母 \(E\)(執行操作 \(1\))，保證最少需要花 \(2\) 個步驟，故最終輸出 \(2\)

子題