Chỉnh sửa

Khoảng cách chỉnh sửa (edit distance) giữa hai xâu là số phép biến đổi ít nhất cần thực hiện để biến xâu này thành xâu kia.

Các phép biến đổi được cho phép là:

• Thêm một kí tự vào xâu;
• Xoá một kí tự khỏi xâu;
• Thay một kí tự trong xâu bằng một kí tự khác.

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

Yêu cầu. Hãy tính khoảng cách chỉnh sửa giữa hai xâu cho trước.

Input

• Dòng đầu tiên chứa một xâu gồm \(n\) kí tự in hoa từ A đến Z.
• Dòng thứ hai chứa một xâu gồm \(m\) kí tự in hoa từ A đến Z.
• Ràng buộc: \(1 \le n, m \le 5000\).

Output

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

Input

%
LOVE
MOVIE

Output

%
2

Notes

Trong ví dụ, ta biến LOVE thành MOVIE qua hai bước: thay L thành M được MOVE, rồi thêm I được MOVIE. Không có cách nào dùng ít hơn hai phép biến đổi, nên đáp án là \(2\).

Scoring

• (\(50\%\)) \(1 \le n, m \le 100\);
• (\(50\%\)) Không có ràng buộc thêm.