Độ dài thay đổi

Trong một buổi họp với giám đốc nhân sự, FullHouse Dev được giao một bài toán thú vị. Họ cần tính toán độ dài chỉnh sửa giữa hai chuỗi để xác định số lượng thao tác tối thiểu cần thiết để biến chuỗi này thành chuỗi kia. Các thao tác cho phép bao gồm thêm, xóa hoặc thay thế một ký tự.

Bài toán

FullHouse Dev cần tính toán độ dài chỉnh sửa giữa hai chuỗi \(S_1\) và \(S_2\). Độ dài chỉnh sửa là số lượng thao tác tối thiểu cần thực hiện để biến chuỗi \(S_1\) thành chuỗi \(S_2\).

INPUT FORMAT:

• Dòng đầu tiên chứa chuỗi \(S_1\) có độ dài \(n\) (1 ≤ \(n\) ≤ 5000).
• Dòng tiếp theo chứa chuỗi \(S_2\) có độ dài \(m\) (1 ≤ \(m\) ≤ 5000).

OUTPUT FORMAT:

• In ra một số nguyên: độ dài 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

• Để biến chuỗi "LOVE" thành "MOVIE", bạn có thể thay thế ký tự L bằng M và thêm ký tự I, do đó độ dài chỉnh sửa là 2.