Nhóm đồ án của Trường Công nghệ Thông tin và Truyền thông đang xây dựng chức năng gợi ý sửa lỗi chính tả cho ô tìm kiếm trên cổng thông tin sinh viên. Khi người dùng gõ một từ ~a~, hệ thống so sánh ~a~ với từng từ ~b~ trong từ điển và ưu tiên gợi ý những từ "gần" với ~a~ nhất.

Độ gần được đo bằng số thao tác ít nhất cần thực hiện để biến xâu ~a~ thành xâu ~b~, trong đó mỗi thao tác thuộc một trong ba loại:

• chèn một ký tự vào một vị trí bất kỳ của xâu (kể cả đầu xâu và cuối xâu);
• xoá một ký tự bất kỳ của xâu;
• thay một ký tự bất kỳ của xâu bằng một ký tự khác.

Yêu cầu

Cho hai xâu ~a~ và ~b~, hãy tìm số thao tác ít nhất để biến ~a~ thành ~b~.

Dữ liệu vào

• Dòng thứ nhất chứa xâu ~a~;
• Dòng thứ hai chứa xâu ~b~.

Hai xâu chỉ gồm các chữ cái Latinh thường từ a đến z, viết liền nhau, không có dấu cách.

Kết quả ra

Ghi ra một số nguyên duy nhất là số thao tác ít nhất (bằng ~0~ nếu hai xâu giống hệt nhau).

Ràng buộc

~1 \le |a|, |b| \le 5000~, trong đó ~|s|~ là độ dài của xâu ~s~.

• Subtask 1 (40% số điểm – test 01–08): ~|a|, |b| \le 500~;
• Subtask 2 (30% số điểm – test 09–14): ~|a|, |b| \le 2000~;
• Subtask 3 (30% số điểm – test 15–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

ollimpic
olympics

Kết quả ra mẫu 1

3

Giải thích

Một cách biến đổi dùng ~3~ thao tác: xoá một chữ l (ollimpic ~\to~ olimpic), thay chữ i đầu tiên bằng chữ y (olimpic ~\to~ olympic), rồi chèn chữ s vào cuối xâu (olympic ~\to~ olympics). Không có cách nào dùng ít hơn ~3~ thao tác.