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(1 \leq n \leq 5000)\) ký tự trong khoảng từ A–Z.
Dòng thứ hai có một xâu chứa các ký tự \(m(1 \leq m \leq 5000)\) 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.

Sample Input

LOVE
MOVIE

Sample Output

2