Background

JYY, a programmer in the JSOI kingdom, is addicted to pay-to-win mobile games. He wants to finish his assigned coding tasks as quickly as possible so he can spend more time playing his games.

Description

After reading the coding requirements at light speed, JYY constructs the corresponding code in his mind with incredible speed. The only remaining task is to input it. The program JYY wants to input can be represented as a string consisting of digits $0-9$. He has two ways to input:

1. Directly input a character at the end of the string. Because he is addicted to pay-to-win games, JYY can only afford a terrible keyboard. Inputting a digit $i$ using this keyboard takes $c_i$ time.
2. Copy and paste: JYY can select a substring that has already been input and paste it to the end of the current string. Because he is addicted to pay-to-win games, JYY's mouse is also terrible. For every additional character he selects, he spends $t_c$ time, and he needs an additional $t_p$ time to complete the paste operation. Therefore, the time required to copy a substring of length $L$ and paste it to the end is $t_c \cdot L + t_p$. After the paste is completed, the selected substring is no longer selected (even if he pastes the same substring again, he must select it again).

Now, JYY wants to know the minimum time required to input his desired program using only these two operations.

Input

The first line contains a string $S$ representing the program JYY wants to input.

The second line contains ten positive integers representing $c_0$ to $c_9$, the time required to directly input each digit.

The third line contains two positive integers $t_c$ and $t_p$, representing the time required for the copy-paste operation.

Output

Output a single positive integer representing the minimum total time required.

Constraints

• For 30% of the data, $|S| \le 200$.
• For 100% of the data, $|S| \le 10^5$, $1 \le c_i \le 10^3$, $1 \le t_c, t_p \le 10^4$.

Examples

Input 1

0123
1 2 3 4 5 6 7 8 9 10
1 1

Output 1

10

Input 2

1111111
1 2 1 1 1 1 1 1 1 1
1 1

Output 2

11