#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Edit Distance - Classic Problems | Repovive

CLS6. Edit Distance

1s256 MB

Given two strings $s$ and $t$ , find the minimum number of operations to convert $s$ into $t$ .

Allowed operations:

Insert a character
Delete a character
Replace a character

Constraints

$0 \le |s|, |t| \le 1000$
Strings contain only lowercase English letters

Input

\begin{array}{l} s \\ t \end{array}

Output

$ops$

Samples

Input

kat
cat

Explanation

For this input, the required output is 1.

Output

Input

sitting
kitten

Explanation

For this input, the required output is 3.

Output

Input

flaw
lawn

Explanation

For this input, the required output is 2.

Output

Given two strings $s$ and $t$ , find the minimum number of operations to convert $s$ into $t$ .

Allowed operations:

Insert a character
Delete a character
Replace a character

$0 \le |s|, |t| \le 1000$
Strings contain only lowercase English letters

\begin{array}{l} s \\ t \end{array}

$ops$