You are given two strings ~a~ and ~b~. In 1 operation you can do one of the following:

• Remove a character from ~a~
• Insert a character into ~a~
• Replace a character in ~a~ with another character.

What is the number of operations to turn the string ~a~ into ~b~.

Input

The first line will contain the string ~a~. The second line will contain the string ~b~.

Output

Output the minimum number of operations to turn the string ~a~ into ~b~.

Constraints

• ~1 \le | a |, | b | \le 10^3~

Example 1

Input

bbababbbab
ababbabbbb

Output

3

Example 2

Input

eadbeadcbc
bebbbceeca

Output

8

Example 3

Input

ebdccedbcbbdddcedeab
abdcbcaaeababddedbcd

Output

12