Cho hai chuỗi ký tự ~s_1~ và ~s_2~ chỉ chứa các ký tụ là chữ cái Latin (~a-z, A-Z~).

Hãy tìm số phép lần biến đổi ít nhất cần thực hiện để biến chuỗi ~s_1~ thành chuỗi ~s_2~.

Các phép biến đổi cho phép gồm:

• Thêm một ký tự vào chuỗi.
• Xóa một ký tự ra khỏi chuỗi.
• Thay thế một ký tự bằng ký tự khác.

Yêu cầu: Tính và in ra số phép biến đổi tối thiểu cần để biến ~s_1~ thành ~s_2~.

Input

• Dòng thứ nhất: Chuỗi ký tự ~s_1~ (~1 \leq |s_1| \leq 2000~).
• Dòng thứ hai: Chuỗi ký tự ~s_2~ (~1 \leq |s_2| \leq 2000~).

Output

Một số nguyên duy nhất — khoảng cách edit nhỏ nhất giữa hai chuỗi.

Example input 1

raccoonoj
clueoj

Example output 1

3

Note 1

• Biến đổi raccoonoj → clueoj như sau:
  • raccoonoj → accoonoj (xóa r tại vị trí 1).
  • accoonoj → ccoonoj (xóa a tại vị trí 1).
  • ccoonoj → coonoj (xóa c tại vị trí 1).
  • coonoj → clonoj (thay o tại vị trí 2 thành l).
  • clonoj → clunoj (thay o tại vị trí 3 thành u).
  • clunoj → clueoj (thay n tại vị trí 4 thành e).