Hai xâu kí tự ~X~ và ~Y~ được gọi là hai xâu họ hàng nếu mỗi kí tự có ở xâu này đều có ở xâu kia và ngược lại. Hai xâu rỗng cũng được xem là hai xâu họ hàng.

Ví dụ: ~X =~ aabccdcbe và ~Y =~ abcde là hai xâu họ hàng.

Cho hai xâu kí tự ~S_1~ và ~S_2~ chỉ gồm các chữ cái in thường từ a đến z. Để biến hai xâu này thành xâu họ hàng, bạn được phép thực hiện hai thao tác sau với số lần tùy ý (có thể không thực hiện):

• Xóa một kí tự bất kỳ khỏi ~S_1~ hoặc ~S_2~. Chi phí cho mỗi lần xóa là ~A~.
• Chèn thêm một kí tự bất kỳ (từ a đến z) vào một vị trí bất kỳ trong ~S_1~ hoặc ~S_2~. Chi phí cho mỗi lần chèn là ~B~.

Yêu cầu: Hãy tính tổng chi phí ít nhất cần bỏ ra để biến ~S_1~ và ~S_2~ thành hai xâu họ hàng.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~A~ và ~B~ ~(1 \le A, B \le 10^9)~ lần lượt là chi phí cho một lần xóa và một lần chèn.
• Dòng thứ hai chứa xâu kí tự ~S_1~.
• Dòng thứ ba chứa xâu kí tự ~S_2~.
• Dữ liệu đảm bảo độ dài mỗi xâu không vượt quá ~10^6~ kí tự và chỉ chứa các chữ cái in thường.

Kết quả

• In ra một số nguyên duy nhất là tổng chi phí tối thiểu để hai xâu trở thành xâu họ hàng.

Ví dụ

Input

5 2
aabbcc
ab

Output

2

Giải thích: ~S_1~ có chứa kí tự c trong khi ~S_2~ thì không. Cách tốn ít chi phí nhất là thực hiện 1 thao tác: chèn thêm kí tự c vào xâu ~S_2~. Tổng chi phí là ~2~.

Giới hạn

• ~1 \le A, B \le 10^9~.
• ~|S_1|, |S_2| \le 10^6~ (trong đó ~|S_1|, |S_2|~ lần lượt là độ dài của xâu ~S_1~ và ~S_2~).

Subtask:

• Có 40% số test tương ứng với 40% số điểm có ~|S_1|, |S_2| \le 10^3~.
• Có 40% số test tương ứng với 40% số điểm có ~A = 1, B = 10^9~.
• Có 20% số test tương ứng với 20% số điểm không có giới hạn gì thêm.