Tý đang làm bài văn tả cảnh quê hương gửi bạn ở xa. Khổ nỗi, do gõ vội, Tý gõ sai một số chỗ và cả xâu đang là \(S\) trong khi xâu đúng phải là \(T\). Để sửa lỗi, mỗi lần Tý chỉ được chọn một trong ba thao tác: chèn thêm một ký tự bất kỳ vào bất kỳ chỗ nào, xoá đi một ký tự bất kỳ, hoặc thay một ký tự bằng một ký tự khác. Tý muốn tìm cách sửa càng ít thao tác càng tốt vì mỗi lần sửa đều tốn công đọc lại.

Hãy giúp Tý tính số thao tác ít nhất cần thực hiện để biến xâu \(S\) thành xâu \(T\).

Định dạng đầu vào

• Dòng đầu tiên chứa xâu \(S\) (độ dài \(|S| \le 5000\)).
• Dòng thứ hai chứa xâu \(T\) (độ dài \(|T| \le 5000\)).

Định dạng đầu ra

• In ra số thao tác ít nhất.

Ví dụ

Input:

kitten
sitting

Output:

3

Ràng buộc

• \(30\%\) số điểm ứng với \(|S|, |T| \le 100\).
• \(30\%\) số điểm ứng với \(|S|, |T| \le 1000\).
• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.