Cho hai xâu ~s~ và ~t~. Với mỗi một thao tác, bạn có thể xóa một ký tự trong ~s~ hoặc chèn một ký tự vào vị trí bất kỳ trong ~s~. Đếm số lượng thao tác ít nhất để biến đổi xâu ~s~ thành xâu ~t~.

Input Specification: Data taken from TRANS.INP

• Dòng đầu tiên chứa xâu ký tự ~s~.
• Dòng thứ hai chứa xâu ký tự ~t~.

Output Specification: Data written in TRANS.OUT

• Một dòng duy nhất là kết quả bài toán.

Subtasks

• Subtask #1 [30%]: Xâu ~s~ và ~t~ có độ dài không quá ~20~.
• Subtask #2 [30%]: Xâu ~s~ và ~t~ có độ dài không quá ~2000~.
• Subtask #3 [40%]: Xâu ~s~ và ~t~ có độ dài không quá ~10000~.

Sample Cases

Input #1:

nguyenkhanhphuc
danghuyhau

Output #1:

11

Explanation #1:

• Xóa các ký tự thứ ~5~ đến thứ ~7~ trong xâu ~s~ mất ba thao tác, ta được nguyhanhphuc.
• Chèn các ký tự da vào vị trí đầu tiên của xâu ~s~ mất hai thao tác, ta được danguyhanhphuc.
• Chèn ký tự h vào vị trí thứ ~5~ trong xâu ~s~ mất một thao tác, ta được danghuyhanhphuc.
• Xóa các ký tự thứ ~14~ đến thứ ~17~ trong xâu ~s~ mất bốn thao tác, ta được danghuyhauc.
• Xóa ký tự thứ ~12~ trong xâu ~s~ mất một thao tác, ta được danghuyhau.