Bạn đang chơi một trò chơi online. Để qua được mức mới, bạn phải tạo ra một khóa đúng bằng một xâu mục tiêu ~s~ (chỉ gồm chữ cái latin thường), có độ dài ~n~. Bạn bắt đầu từ xâu rỗng và được phép thực hiện các thao tác sau:

• Thêm 1 ký tự vào cuối xâu đang có, tốn thời gian ~a~.
• Gấp đôi xâu hiện tại: gắn thêm chính xâu đang có vào cuối nó (tức là biến ~t~ thành ~t+t~), tốn thời gian ~b~.
• Xóa ký tự cuối của xâu đang có (chỉ khi xâu không rỗng), tốn thời gian ~c~.

Bạn chỉ qua được mức mới nếu tổng thời gian tạo khóa là nhỏ nhất.

Yêu cầu

Tính thời gian nhỏ nhất để tạo ra đúng xâu ~s~ từ xâu rỗng bằng các thao tác trên.

Dữ liệu

• Dòng 1: số nguyên ~n~ (~1 \le n \le 10^5~).
• Dòng 2: xâu ~s~ (gồm các ký tự thường, độ dài đúng ~n~).
• Dòng 3: ba số nguyên ~a, b, c~ (~0 \le a, b, c \le 10^9~).

Kết quả

In ra một số nguyên: thời gian nhỏ nhất cần thiết để tạo được xâu ~s~.

Ví dụ

Ví dụ 1

Input

7
abcdabc
1 2 0

Output

6

Giải thích

Ví dụ 1

Một cách tối ưu:

• Gõ lần lượt ~a,b,c,d~: tạo được abcd, tốn ~4 \cdot a = 4~.
• Gấp đôi: abcd → abcdabcd, tốn ~b = 2~.
• Xóa ký tự cuối: abcdabcd → abcdabc, tốn ~c = 0~.

Tổng thời gian: ~4 + 2 + 0 = 6~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^5~
• ~s~ chỉ gồm chữ cái thường, ~|s| = n~
• ~0 \le a, b, c \le 10^9~