두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다.</p>

A에 적용할 수 있는 연산은 총 4가지가 있으며 아래와 같다.

1. 삽입: A의 한 위치에 문자 하나를 삽입한다.
2. 삭제: A의 문자 하나를 삭제한다.
3. 교체: A의 문자 하나를 다른 문자로 교체한다.
4. 교환: A의 인접한 두 문자의 위치를 서로 바꾼다.

두 문자열이 주어졌을 때, 최소 편집 횟수를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력 형식

첫째 줄에 최소 편집 횟수를 출력한다.

예제 입력 1

abc
ab

예제 출력 1

1

예제 입력 2

ca
abc

예제 출력 2

2

예제 입력 3

abc
cba

예제 출력 3

2

예제 입력 4

abcd
bcde

예제 출력 4

2

예제 입력 5

abababababa
aaabbbbbaaa

예제 출력 5

4

예제 입력 6

baab
abba

예제 출력 6

2

예제 입력 7

ababababab
bababababa

예제 출력 7

2

예제 입력 8

abcdefghijkl
badcfehgjilk

예제 출력 8

6

예제 입력 9

axxayyazza
azzayyaxxa

예제 출력 9

4

예제 입력 10

axxayyazza
xaaxyyzaaz

예제 출력 10

4