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.

Output

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

Constraints

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

Example

Sample input

LOVE
MOVIE

Sample output

2