Cho \(2\) xâu \(s1\) và \(s2\). Hãy biến đổi xâu \(s1\) thành xâu \(s2\) hoặc ngược lại. Có \(3\) phép biến đổi như sau:

• Thêm một ký tự vào chuỗi.
• Xóa một ký tự
• Thay thế một ký tự trong chuỗi.

Input

• Dòng một là chuỗi \(s1\)
• Dòng hai là chuỗi \(s2\)

Output

• Số phép biến đổi ít nhất

Điều kiện

• \(1 \le n,m \le 5000\)

Sample Input 1

LOVE
MOVIE

Sample Output 1

2