Khoảng cách chỉnh sửa giữa hai xâu là số lượng thao tác tối thiểu cần thiết để chuyển đổi một xâu thành xâu kia.

Các thao tác được phép là:

• Thêm một ký tự vào xâu
• Xóa một ký tự khỏi xâu
• Thay thế một ký tự trong xâu

Ví dụ: khoảng cách chỉnh sửa giữa LOVE và MOVIE là \(2\), vì trước tiên bạn có thể thay thế L bằng M, sau đó thêm I.

Nhiệm vụ của bạn là tính toán khoảng cách chỉnh sửa giữa hai xâu.

Input

• Dòng đầu tiên có một xâu chứa \(n\) ký tự trong khoảng từ A–Z
• Dòng thứ hai có một xâu chứa các ký tự \(m\) trong khoảng từ A–Z

Constraints

• \(1 \leq n \leq 5000\)

Output

• In một số nguyên: khoảng cách chỉnh sửa giữa các xâu

Example

LOVE
MOVIE

2