提示: 欢迎访问OurACM平台。
Problem 1434 Edit Distance

Accept: 249    Submit: 691
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

A and B are two strings. We are going to edit the strings using the following operations:
(1) delete a character
(2) insert a character
(3) change a character into another character


We define a function d(A,B) as the minimal operations needed to change string A into string B. Your task is to compute the function according to the given string A and B.

Input

There are multiple test cases. Each case contains two lines. The first line contains the string A, the second contains the string B. The length of each string would not exceed 2000.

Output

Please output the result of d(A,B).

Sample Input

fxpimu xwrs

Sample Output

5

Source

FZU 2006 Summer Training II

Submit  Back  Status  Discuss