편집 거리

문자열 $A$를 문자열 $B$로 바꾸는 편집 스크립트를 생각한다. 편집 스크립트는 아래 네 가지 명령으로 이루어지며, 각 명령은 $A$를 앞에서부터 소비하면서 결과 문자열을 만든다.

• 추가(a): 한 글자를 결과에 출력한다. $A$는 건드리지 않는다.
• 삭제(d): $A$의 맨 앞 글자를 지우고, 아무것도 출력하지 않는다.
• 수정(m): $A$의 맨 앞 글자를 지우고, 대신 다른 한 글자를 결과에 출력한다.
• 복사(c): $A$의 맨 앞 글자를 지우고, 그 글자를 그대로 결과에 출력한다.

복사는 비용이 들지 않는다. 편집 스크립트의 길이는 사용한 추가·삭제·수정 명령의 개수로 정의하며, 가장 짧은 편집 스크립트는 이 세 명령의 개수를 최소로 하는 스크립트이다.

두 문자열 $A$와 $B$가 주어질 때, $A$를 $B$로 바꾸는 가장 짧은 편집 스크립트에서 사용하는 추가·삭제·수정 명령의 최소 개수(편집 거리)를 구하시오.

첫째 줄에 문자열 $A$가, 둘째 줄에 문자열 $B$가 주어진다. 두 문자열은 모두 영문 알파벳(대문자와 소문자)과 숫자로만 이루어지며, 길이는 $1$ 이상 $17000$ 이하이다.

$A$를 $B$로 바꾸는 데 필요한 추가·삭제·수정 명령의 최소 개수를 정수 하나로 출력한다.