Cho ba thao tác thao tác trên xâu rỗng để dựng thành xâu đích ~S~:

• Thêm một ký tự vào cuối xâu với chi phí ~A~.
• Nhân đôi xâu hiện tại với chi phí ~B~.
• Xoá ký tự cuối cùng của xâu với chi phí ~C~. Hãy tính chi phí nhỏ nhất để dựng được xâu ~S~ từ xâu rỗng.

Yêu cầu

Tìm chi phí tối thiểu để xây dựng xâu ~S~ xuất phát từ xâu rỗng, khi được phép sử dụng bất kỳ số lần ba thao tác: thêm một ký tự vào cuối, nhân đôi xâu hiện tại, và xoá ký tự cuối.

Dữ liệu

• Dòng 1: số nguyên ~N~ là độ dài của ~S~ (~1 \le ~N~ \le 10^5~).
• Dòng 2: xâu ~S~ chỉ gồm các chữ cái Latin thường.
• Dòng 3: ba số nguyên ~A, B, C~ (~0 \le ~A, B, C~ \le 10^9~) lần lượt là chi phí của ba thao tác.

Kết quả

In ra một số nguyên là chi phí nhỏ nhất tìm được.

Ví dụ

Ví dụ 1

Input

5
abcab
1 2 0

Output

5

Ví dụ 2

Input

4
aaaa
3 2 100

Output

7

Giải thích

• Ví dụ 1: Một cách tối ưu: thêm 'a','b','c' (chi phí ~3~), nhân đôi "abc" → "abcabc" (chi phí ~+2~), rồi xoá một ký tự cuối để được "abcab" (chi phí ~+0~); tổng ~5~.
• Ví dụ 2: Tối ưu là thêm 'a' (~3~), nhân đôi → "aa" (~+2~), nhân đôi → "aaaa" (~+2~); tổng ~7~. Xoá có chi phí rất lớn nên không dùng.

Chấm điểm

100% số test thoả ràng buộc: $$ 1 \le ~N~ \le 10^5,\quad 0 \le ~A, B, C~ \le 10^9. $$