Problem AN
Bitmask

Masking greatly reduces the transmission of certain viruses. This is true for computer viruses as well. In order to protect binary data from infection, we must cover it up with masks!

Binary data can be represented as a string of $n$ $0$s and $1$s. A bitmask can be used to cover a portion of the data. Specifically, a bitmask of length $m\le n$ can be used to cover $m$ consecutive bits in the data. To maximize protection, only well-fitting masks can be used. That is, each covered bit in the binary data is the opposite to the corresponding bit in the mask. For example, if the data is

then the mask $011$ can be used to cover positions $1$–$3$. The mask $101$ can be used to cover positions $3$–$5$ and $10$–$12$.

The cost to produce a bitmask of length $i$ is $C_i$. Fortunately, if you have already produced a particular bitmask, you can make as many copies as you wish for free! Thus, one can produce two masks of 101 for only $C_3$.

What is the minimum cost to cover a particular piece of binary data with bitmasks? Every bit in the data must be covered by exactly one bitmask.

Input

The first line of input consists of a string of $0$s and $1$s representing the binary data. The length of the string $n$ satisfies $1\le n\le 12$. The second line of input consists of $n$ integers $C_1,\dots ,C_n$, where $1\le C_i\le 100$.

Output

Output the minimum cost to produce the bitmasks to cover the binary data.

10101010
2 3 7 1 4 3 8 9

1

101010101111
26 51 24 79 15 46 22 79 47 84 60 100

37