Bài toán: Tính khoảng cách chỉnh sửa giữa hai chuỗi

Đề bài

Khoảng cách chỉnh sửa (edit distance) giữa hai chuỗi là số lượng thao tác tối thiểu cần thực hiện để biến chuỗi này thành chuỗi kia.

Các thao tác được phép bao gồm:

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

Ví dụ:

• Khoảng cách chỉnh sửa giữa "LOVE" và "MOVIE" là 2, vì bạn có thể:
  • Thay thế "L" bằng "M".
  • Thêm "I".

Input

• Dòng đầu tiên chứa chuỗi thứ nhất có độ dài ~ n ~ (~ 1 \leq n \leq 5000 ~).
• Dòng thứ hai chứa chuỗi thứ hai có độ dài ~ m ~ (~ 1 \leq m \leq 5000 ~).

Output

• In ra một số nguyên: khoảng cách chỉnh sửa giữa hai chuỗi.

Ràng buộc

• ~ 1 \leq n, m \leq 5000 ~

Ví dụ

Input:

LOVE
MOVIE

Output:

2

Giải thích:

• Bạn có thể thay "L" thành "M", và thêm "I" vào chuỗi "LOVE" để biến nó thành "MOVIE".